Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A necklace in an undirected graph is a sequence of cycles C₁, C₂,..., C_k(k1) , satisfying the conditions below:

1. Any two cycles have no edges in common.
2. There is exactly one common vertex between two adjacent cycles C_i and C_i+1 (1i < k)
3. Any two non-adjacent cycles are vertex disjoint, i.e. no vertices in common.

Note that any vertex appears in a cycle at most once.

A necklace between two vertices S and T is a necklace C₁, C₂,..., C_k such that S belongs to C₁ and T belongs to C_k .

Given an undirected graph and two vertices S and T , you need find whether a necklace between S and T exists.

Input 

The input consists of multiple test cases. Each test case starts with a line containing two integers N (2N10, 000) and M (1M100, 000) , which are the number of vertices and the number of edges in the undirected graph, respectively.

Each of the following M lines contains two integers A and B (1A BN) , which indicates an undirected edge between vertices A and B . Vertices are numbered from 1 to N .

The last line of each test case contains two integers S and T (1S TN) .

The last test case is followed by a line containing two zeros.

Output 

For each test case, print a line containing the test case number (beginning with 1) followed by ``YES", if the required necklace exists, otherwise ``NO".

Sample Input 

3 3 
1 2 
2 3
3 1 
1 3 
4 5 
1 2 
2 3 
1 3 
3 4 
3 4 
1 4 
4 5 
1 2 
1 2 
2 3 
3 4 
3 4 
1 4 
0 0

Sample Output 

Case 1: YES 
Case 2: YES 
Case 3: NO

---

題目描述：

在圖中可以找到多個環，而相鄰的環(Ci, Ci+1)只會有一個交點。

而且每個環使用的邊都不會重疊，因此看起來就像是環環環所構成的鍊。

而題目問當 S 在第一環，而 T 在最後一環，問是否存在這一個鍊。

題目解法：

題目講得很冗長，事實上不用考慮那麼多環，當 k > 1 時，事實上都等同於 k = 1。

也就是一個環就可以了，點可以重複使用。

當 k = 1 時，相當於從 S 到 T 有兩條不相交的路徑。

問題變成「在無權無向圖中，查找 S 到 T 的兩條不相交路徑。」

使用 maxflow 去解決，增一個點 x 到 S 容量是 2，而相連的邊容量都是 1。

查看 x 到 T 的最大流是否為 2。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[500005];
int e, head[10005], dis[10005], prev[10005], record[10005];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 0;
    edge[e].next = head[y], head[y] = e++;
}
int maxflow(int s, int t) {
    int flow = 0;
    int i, j, x, y;
    while(1) {
        memset(dis, 0, sizeof(dis));
        dis[s] =  0xffff; // oo
        queue<int> Q;
        Q.push(s);
        while(!Q.empty()) {
            x = Q.front();
            Q.pop();
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(dis[y] == 0 && edge[i].v > 0) {
                    prev[y] = x, record[y] = i;
                    dis[y] = min(dis[x], edge[i].v);
                    Q.push(y);
                }
            }
            if(dis[t])  break;
        }
        if(dis[t] == 0) break;
        flow += dis[t];
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].v -= dis[t];
            edge[ri^1].v += dis[t];
        }
    }
    return flow;
}
int main() {
    int n, m;
    int cases = 0;
    int i, j, k, x, y;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        e = 0;
        memset(head, -1, sizeof(head));
        int S, T;
        for(i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            addEdge(x, y, 1);
            addEdge(y, x, 1);
        }
        S = 0;
        scanf("%d %d", &x, &T);
        addEdge(S, x, 2);
        int flow = maxflow(S, T);
        printf("Case %d: %s\n", ++cases, flow == 2 ? "YES" : "NO");
    }
    return 0;
}