UVa 10480：Sabotage （最小割集）

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1421

题意：给出n个点m条边，每条边有一个花费，问将1和2隔离需要破坏的边的最小花费的边集。

思路：很明显是最小割，但是问题在于如何求出这个最小割集。通过以前的题目，求网络的最大流就是求网络的最小割，那么从源点到汇点的最大流必定就会经过最小割集的边，当这条边满载（flow == cap）的时候，这条边其实就是最小割集的边。求出最大流之后，整个残余网络会被分成两个集合，一个和源点直接间接相连的点集，另一个和汇点直接间接相连的点集，所以只要BFS从源点或者汇点往前扫，一边扫一边标记，直到扫到（flow == cap）的边就停止。然后枚举边，如果一条边有一边的顶点是被标记过的，另一边的顶点没被标记，那么这条边就是最小割集之一了。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <string>
  7 #include <iostream>
  8 #include <stack>
  9 #include <map>
 10 #include <queue>
 11 #include <set>
 12 using namespace std;
 13 typedef long long LL;
 14 #define N 55
 15 #define M 505
 16 #define INF 0x3f3f3f3f
 17 struct Edge {
 18     int u, v, cap;
 19     Edge () {}
 20     Edge (int u, int v, int cap) : u(u), v(v), cap(cap) {}
 21 } edge[M*4];
 22 vector<int> G[N];
 23 int dis[N], cur[N], S, T, tot, vis[N], mp[N][N];
 24 
 25 void Add(int u, int v, int cap) {
 26     edge[tot] = Edge(u, v, cap);
 27     G[u].push_back(tot++);
 28     edge[tot] = Edge(v, u, 0);
 29     G[v].push_back(tot++);
 30 }
 31 
 32 int BFS() {
 33     memset(dis, INF, sizeof(dis));
 34     queue<int> que;
 35     que.push(S); dis[S] = 0;
 36     while(!que.empty()) {
 37         int u = que.front(); que.pop();
 38         for(int i = 0; i < G[u].size(); i++) {
 39             Edge &e = edge[G[u][i]];
 40             if(dis[e.v] == INF && e.cap > 0) {
 41                 dis[e.v] = dis[u] + 1;
 42                 que.push(e.v);
 43             }
 44         }
 45     }
 46     return dis[T] < INF;
 47 }
 48 
 49 int DFS(int u, int maxflow) {
 50     if(u == T) return maxflow;
 51     for(int i = cur[u]; i < G[u].size(); i++) {
 52         cur[u] = i;
 53         Edge &e = edge[G[u][i]];
 54         if(dis[e.v] == dis[u] + 1 && e.cap > 0) {
 55             int flow = DFS(e.v, min(e.cap, maxflow));
 56             if(flow > 0) {
 57                 e.cap -= flow;
 58                 edge[G[u][i]^1].cap += flow;
 59                 return flow;
 60             }
 61         }
 62     }
 63     return 0;
 64 }
 65 
 66 int Dinic() {
 67     int ans = 0;
 68     while(BFS()) {
 69         int flow;
 70         memset(cur, 0, sizeof(cur));
 71         while(flow = DFS(S, INF)) ans += flow;
 72     }
 73     return ans;
 74 }
 75 
 76 void bfs() {
 77     queue<int> que;
 78     que.push(S); vis[S] = 1;
 79     while(!que.empty()) {
 80         int u = que.front(); que.pop();
 81         for(int i = 0; i < G[u].size(); i++) {
 82             Edge &e = edge[G[u][i]];
 83             if(!vis[e.v] && e.cap > 0) {
 84                 vis[e.v] = 1;
 85                 que.push(e.v);
 86             }
 87         }
 88     }
 89 }
 90 
 91 int main()
 92 {
 93     int n, m;
 94     while(~scanf("%d%d", &n, &m), n + m) {
 95         int u, v, cap; tot = 0;
 96         for(int i = 1; i <= n; i++) G[i].clear();
 97         memset(mp, 0, sizeof(mp));
 98         memset(vis, 0, sizeof(vis));
 99         for(int i = 0; i < m; i++) {
100             scanf("%d%d%d", &u, &v, &cap);
101             Add(u, v, cap); Add(v, u, cap);
102         } S = 1, T = 2;
103         Dinic();
104         bfs();
105         for(int u = 1; u <= n; u++) {
106             for(int i = 0; i < G[u].size(); i++) {
107                 int v = edge[G[u][i]].v;
108                 if(vis[u] && !vis[v] || vis[v] && !vis[u]) mp[u][v] = mp[v][u] = 1;
109             }
110         }
111         for(int i = 1; i <= n; i++) {
112             for(int j = i + 1; j <= n; j++) {
113                 if(mp[i][j]) printf("%d %d
", i, j);
114             }
115         }
116         puts("");
117     }
118     return 0;
119 }