ZOJ_2587

? ? 這個(gè)題目本質(zhì)上就是去判斷最小割是否為1，在做完最大流之后的圖上，我們從S出發(fā)沿非滿(mǎn)流的邊能走到的點(diǎn)一定是屬于S集合的，其余能夠沿非滿(mǎn)流邊走到T的點(diǎn)一定是屬于T集合的，如果這時(shí)還沒(méi)有覆蓋所有的點(diǎn)，那么那些點(diǎn)就既可以看作是S集合的，也可以看作是T集合的，自然最小割就不唯一了。

#include<stdio.h> #include<string.h> #include<algorithm> #define MAXD 810 #define MAXM 20010 #define INF 0x3f3f3f3f int N, M, first[MAXD], e, next[MAXM], v[MAXM], flow[MAXM]; int S, T, d[MAXD], q[MAXD], work[MAXD], vis[MAXD]; void add(int x, int y, int z) {v[e] = y, flow[e] = z;next[e] = first[x], first[x] = e ++; } void init() {int i, x, y, z;memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0;for(i = 0; i < M; i ++){scanf("%d%d%d", &x, &y, &z);add(x, y, z), add(y, x, z); } } int bfs() {int i, j, rear = 0;memset(d, -1, sizeof(d[0]) * (N + 1));d[S] = 0, q[rear ++] = S;for(i = 0; i < rear; i ++)for(j = first[q[i]]; j != -1; j = next[j])if(flow[j] && d[v[j]] == -1){d[v[j]] = d[q[i]] + 1, q[rear ++] = v[j];if(v[j] == T) return 1; }return 0; } int dfs(int cur, int a) {if(cur == T) return a;for(int &i = work[cur]; i != -1; i = next[i])if(flow[i] && d[v[i]] == d[cur] + 1)if(int t = dfs(v[i], std::min(a, flow[i]))){flow[i] -= t, flow[i ^ 1] += t;return t; } return 0; } void DFS(int cur, int k) {int i;vis[cur] = 1;for(i = first[cur]; i != -1; i = next[i])if(flow[i ^ k] != 0 && !vis[v[i]])DFS(v[i], k); } void dinic() {while(bfs()){memcpy(work, first, sizeof(first[0]) * (N + 1));while(dfs(S, INF)); } } int check() {for(int i = 1; i <= N; i ++) if(!vis[i]) return 0;return 1; } void solve() {dinic();memset(vis, 0, sizeof(vis[0]) * (N + 1));DFS(S, 0), DFS(T, 1);printf("%s\n", check() ? "UNIQUE" : "AMBIGUOUS"); } int main() {while(scanf("%d%d%d%d", &N, &M, &S, &T), N){init();solve(); }return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/staginner/archive/2012/08/18/2645398.html

總結(jié)

以上是生活随笔為你收集整理的ZOJ 2587 Unique Attack的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。