[UVA][maxflow] 1242 - Necklace
A necklace in an undirected graph is a sequence of cycles
C1, C2,..., Ck(k
1)
, satisfying the conditions below:
- Any two cycles have no edges in common.
- There is exactly one common vertex between two adjacent cycles Ci
and Ci+1
(1
i < k)
- 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 C1, C2,..., Ck such that S belongs to C1 and T belongs to Ck .
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;
}