题意：给定一个无向图，要求判定分离两个点的最小割是否唯一。
解法：在求出最大流的基础上，从源点进行一次搜索，搜索按照未饱和的边进行，得到顶点子集S的顶点个数；再从汇点反向搜索未饱和的边，得到子集T的顶点个数，判定顶点数相加是否等于总共的顶点数。
http://blog.csdn.net/waitfor_/article/details/7330437的文章写的很好，这里截取文中所画的两个图进行说明。
(1)正向搜索集合为S，反向搜索集合为T，cnt1和cnt2都是最小割边。很显然M还存在着最小割边，因为从M到T的残余网络也没有流向T的容量了。
(2)增加E1这部分边的容量将直接导致网络最大流量增加。增加E2和E3则不然。同样M中存在并上E1后为割边的边集。
(3)两条割边完全重合为一条，此时网络中的割边唯一。
代码如下：
View Code #include#include #include #include #include using namespace std;const int SS = 805, TT = 806;const int INF = 0x3fffffff;int N, M, A, B;struct Edge { int v, c, next; };Edge e[30000];int idx, head[810], lv[810];int front, tail, que[810];int vis[810];void insert(int a, int b, int c) { e[idx].v = b, e[idx].c = c; e[idx].next = head[a]; head[a] = idx++;}bool bfs() { memset(lv, 0xff, sizeof (lv)); front = tail = lv[SS] = 0; que[tail++] = SS; while (front < tail) { int u = que[front++]; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if (!(~lv[v]) && e[i].c) { lv[v] = lv[u] + 1; if (v == TT) return true; que[tail++] = v; } } } return false;}int dfs(int u, int sup) { if (u == TT) return sup; int tf = 0, f; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if (lv[u]+1==lv[v] && e[i].c && (f=dfs(v, min(e[i].c, sup-tf)))) { tf += f; e[i].c -= f, e[i^1].c += f; if (tf == sup) return sup; } } if (!tf) lv[u] = -1; return tf;}void dinic() { int ret = 0; while (bfs()) { ret += dfs(SS, INF); }// printf("ret = %d\n", ret); }void flood(int u, int &cnt) { for (int i = head[u]; i != -1; i = e[i].next) { if (e[i].c && !vis[e[i].v]) { ++cnt; vis[e[i].v] = 1; flood(e[i].v, cnt); } }}void flood_r(int u, int &cnt) { for (int i = head[u]; i != -1; i = e[i].next) { if (e[i^1].c && !vis[e[i].v]) { ++cnt; vis[e[i].v] = 1; flood_r(e[i].v, cnt); } }}bool query() { int cnta = 0, cntb = 0; // 分别为从两个方向进行搜索而计数 memset(vis, 0, sizeof (vis)); vis[SS] = vis[TT] = 1; flood(SS, cnta); memset(vis, 0, sizeof (vis)); vis[SS] = vis[TT] = 1; flood_r(TT, cntb); return cnta + cntb == N;}int main() { while (scanf("%d %d %d %d", &N, &M, &A, &B), N|M|A|B) { int a, b, c; idx = 0; memset(head, 0xff, sizeof (head)); insert(SS, A, INF), insert(A, SS, 0); insert(B, TT, INF), insert(TT, B, 0); for (int i = 0; i < M; ++i) { scanf("%d %d %d", &a, &b, &c); insert(a, b, c), insert(b, a, c); } dinic(); printf(query() ? "UNIQUE\n" : "AMBIGUOUS\n"); } return 0; }