首页 > 代码库 > POJ 2914 Minimum Cut
POJ 2914 Minimum Cut
Minimum Cut
Time Limit: 10000ms
Memory Limit: 65536KB
This problem will be judged on PKU. Original ID: 291464-bit integer IO format: %lld Java class name: Main
Given an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must be removed at least to disconnect the graph into two subgraphs?
Input
Input contains multiple test cases. Each test case starts with two integers N and M (2 ≤ N ≤ 500, 0 ≤ M ≤ N × (N − 1) ⁄ 2) in one line, where N is the number of vertices. Following areM lines, each line contains M integers A, B and C (0 ≤ A, B < N, A ≠ B, C > 0), meaning that there C edges connecting vertices A and B.
Output
There is only one line for each test case, which contains the size of the minimum cut of the graph. If the graph is disconnected, print 0.
Sample Input
3 30 1 11 2 12 0 14 30 1 11 2 12 3 18 140 1 10 2 10 3 11 2 11 3 12 3 14 5 14 6 14 7 15 6 15 7 16 7 14 0 17 3 1
Sample Output
212
Source
Baidu Star 2006 Semifinal
解题：无向图的最小割。Stoer-Wagner 算法
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 510;18 int e[maxn][maxn],n,m;19 bool comb[maxn];20 int Find(int &s,int &t){21 bool vis[maxn];22 int w[maxn];23 memset(vis,false,sizeof(vis));24 memset(w,0,sizeof(w));25 int tmp = INF;26 for(int i = 0; i < n; ++i){27 int theMax = -INF;28 for(int j = 0; j < n; j++)29 if(!vis[j] && !comb[j] && w[j] > theMax)30 theMax = w[tmp = j];31 if(t == tmp) break;32 s = t;33 vis[t = tmp] = true;34 for(int j = 0; j < n; j++)35 if(!vis[j] && !comb[j])36 w[j] += e[t][j];37 }38 return w[t];39 }40 int solve(){41 int ans = INF,s,t;42 memset(comb,0,sizeof(comb));43 for(int i = 1; i < n; i++){44 s = t = -1;45 ans = min(ans,Find(s,t));46 for(int j = 0; j < n; j++){47 e[s][j] += e[t][j];48 e[j][s] += e[j][t];49 }50 comb[t] = true;51 }52 return ans;53 }54 int main() {55 int u,v,w;56 while(~scanf("%d %d",&n,&m)){57 memset(e,0,sizeof(e));58 while(m--){59 scanf("%d %d %d",&u,&v,&w);60 e[u][v] += w;61 e[v][u] += w;62 }63 printf("%d\n",solve());64 }65 return 0;66 }
POJ 2914 Minimum Cut
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。