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）的边就停止。然后枚举边，如果一条边有一边的顶点是被标记过的，另一边的顶点没被标记，那么这条边就是最小割集之一了。

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 #include <algorithm>

 #include <string>

 #include <iostream>

 #include <stack>

 #include <map>

 #include <queue>

 #include <set>

 using namespace std;

 typedef long long LL;

 #define N 55

 #define M 505

 #define INF 0x3f3f3f3f

 struct Edge {

     int u, v, cap;

     Edge () {}

     Edge (int u, int v, int cap) : u(u), v(v), cap(cap) {}

 } edge[M*];

 vector<int> G[N];

 int dis[N], cur[N], S, T, tot, vis[N], mp[N][N];

 void Add(int u, int v, int cap) {

     edge[tot] = Edge(u, v, cap);

     G[u].push_back(tot++);

     edge[tot] = Edge(v, u, );

     G[v].push_back(tot++);

 }

 int BFS() {

     memset(dis, INF, sizeof(dis));

     queue<int> que;

     que.push(S); dis[S] = ;

     while(!que.empty()) {

         int u = que.front(); que.pop();

         for(int i = ; i < G[u].size(); i++) {

             Edge &e = edge[G[u][i]];

             if(dis[e.v] == INF && e.cap > ) {

                 dis[e.v] = dis[u] + ;

                 que.push(e.v);

             }

         }

     }

     return dis[T] < INF;

 }

 int DFS(int u, int maxflow) {

     if(u == T) return maxflow;

     for(int i = cur[u]; i < G[u].size(); i++) {

         cur[u] = i;

         Edge &e = edge[G[u][i]];

         if(dis[e.v] == dis[u] +  && e.cap > ) {

             int flow = DFS(e.v, min(e.cap, maxflow));

             if(flow > ) {

                 e.cap -= flow;

                 edge[G[u][i]^].cap += flow;

                 return flow;

             }

         }

     }

     return ;

 }

 int Dinic() {

     int ans = ;

     while(BFS()) {

         int flow;

         memset(cur, , sizeof(cur));

         while(flow = DFS(S, INF)) ans += flow;

     }

     return ans;

 }

 void bfs() {

     queue<int> que;

     que.push(S); vis[S] = ;

     while(!que.empty()) {

         int u = que.front(); que.pop();

         for(int i = ; i < G[u].size(); i++) {

             Edge &e = edge[G[u][i]];

             if(!vis[e.v] && e.cap > ) {

                 vis[e.v] = ;

                 que.push(e.v);

             }

         }

     }

 }

 int main()

 {

     int n, m;

     while(~scanf("%d%d", &n, &m), n + m) {

         int u, v, cap; tot = ;

         for(int i = ; i <= n; i++) G[i].clear();

         memset(mp, , sizeof(mp));

         memset(vis, , sizeof(vis));

         for(int i = ; i < m; i++) {

             scanf("%d%d%d", &u, &v, &cap);

             Add(u, v, cap); Add(v, u, cap);

         } S = , T = ;

         Dinic();

         bfs();

         for(int u = ; u <= n; u++) {

             for(int i = ; i < G[u].size(); i++) {

                 int v = edge[G[u][i]].v;

                 if(vis[u] && !vis[v] || vis[v] && !vis[u]) mp[u][v] = mp[v][u] = ;

             }

         }

         for(int i = ; i <= n; i++) {

             for(int j = i + ; j <= n; j++) {

                 if(mp[i][j]) printf("%d %d\n", i, j);

             }

         }

         puts("");

     }

     return ;

 }

巴特西

UVa 10480：Sabotage （最小割集）

最新文章

热门文章