题意还行,就是问最小割是不是唯一的。
假设源点为s,汇点为t,最小割将点集分为两个点集S,T
那么S的一种情况就是,从源点出发,dfs残留网络,沿着不满流的边走,能走到的所有点都属于S,全集减去S即为T。
T的一种情况是,如果一个点沿着一些不满流的边能到达汇点,那么该点属于T。
而本题要求的是唯一性,观察网络有这样一个特性,一个点如果既不能由S沿着不满流的边到达,也不能沿着一些不满流的边到达T,那么该点既可以属于S,也可属于T,那么最小割不是唯一的。
为什么呢? 如果一个点v不能由S沿着不满流的边到达,必然是S到v的所有边都满流,同样如果v沿着不满流的边到不了T,v到T的所有边也都是满流,并且,S到v的流量等于v到T的流量,否则两边流量不对等会导致不满流的边出现,此时既然流量相等,那么v属于S或者T都是可以的,也就是说最小割不唯一
这里搜索要搜两次,一次是从源点出发,另一次是从汇点出发搜索逆图
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> #include <map> #include <set> #define eps 1e-5 #define MAXN 1111 #define MAXM 55555 #define INF 10000007 using namespace std; struct node { int u, v; // vtex int c; // cacity int f; // current f in this arc int next, r; } edge[MAXM]; int dist[MAXN], nm[MAXN], src, des, n; int head[MAXN], e; void add(int x, int y, int c) { edge[e].u = x; edge[e].v = y; edge[e].c = c; edge[e].f = 0; edge[e].r = e + 1; edge[e].next = head[x]; head[x] = e++; edge[e].u = y; edge[e].v = x; edge[e].c = 0; edge[e].f = 0; edge[e].r = e - 1; edge[e].next = head[y]; head[y] = e++; } void rev_BFS() { int Q[MAXN], h = 0, t = 0; for(int i = 1; i <= n; ++i) { dist[i] = MAXN; nm[i] = 0; } Q[t++] = des; dist[des] = 0; nm[0] = 1; while(h != t) { int v = Q[h++]; for(int i = head[v]; i != -1; i = edge[i].next) { if(edge[edge[i].r].c == 0 || dist[edge[i].v] < MAXN)continue; dist[edge[i].v] = dist[v] + 1; ++nm[dist[edge[i].v]]; Q[t++] = edge[i].v; } } } void init() { e = 0; memset(head, -1, sizeof(head)); } int maxflow() { rev_BFS(); int u; int total = 0; int cur[MAXN], rpath[MAXN]; for(int i = 1; i <= n; ++i)cur[i] = head[i]; u = src; while(dist[src] < n) { if(u == des) // find an augmenting path { int tf = INF; for(int i = src; i != des; i = edge[cur[i]].v) tf = min(tf, edge[cur[i]].c); for(int i = src; i != des; i = edge[cur[i]].v) { edge[cur[i]].c -= tf; edge[edge[cur[i]].r].c += tf; edge[cur[i]].f += tf; edge[edge[cur[i]].r].f -= tf; } total += tf; u = src; } int i; for(i = cur[u]; i != -1; i = edge[i].next) if(edge[i].c > 0 && dist[u] == dist[edge[i].v] + 1)break; if(i != -1) // find an admissible arc, then Advance { cur[u] = i; rpath[edge[i].v] = edge[i].r; u = edge[i].v; } else // no admissible arc, then relabel this vtex { if(0 == (--nm[dist[u]]))break; // GAP cut, Important! cur[u] = head[u]; int mindist = n; for(int j = head[u]; j != -1; j = edge[j].next) if(edge[j].c > 0)mindist = min(mindist, dist[edge[j].v]); dist[u] = mindist + 1; ++nm[dist[u]]; if(u != src) u = edge[rpath[u]].v; // Backtrack } } return total; } int nt, m; int vis[MAXN]; vector<int>g[MAXN]; void dfs1(int u) { vis[u] = 1; for(int i = head[u]; i != -1; i = edge[i].next) if(!vis[edge[i].v] && edge[i].c) dfs1(edge[i].v); } void dfs2(int u) { vis[u] = 1; int size = g[u].size(); for(int i = 0; i < size; i++) if(!vis[g[u][i]]) dfs2(g[u][i]); } int main() { int u, v, w; while(scanf("%d%d%d%d", &nt, &m, &src, &des) != EOF) { init(); if(nt == 0 && m == 0 && src == 0 && des == 0) break; n = nt; for(int i = 1; i <= m; i++) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); } maxflow(); memset(vis, 0, sizeof(vis)); for(int i = 0; i < MAXN; i++) g[i].clear(); for(int i = 0; i < e; i += 2) if(edge[i].c) g[edge[i].v].push_back(edge[i].u); dfs1(src); dfs2(des); int flag = 1; for(int i = 1; i <= nt; i++) if(!vis[i]) flag = 0; if(!flag) printf("AMBIGUOUS\n"); else printf("UNIQUE\n"); } return 0; }