连接:http://poj.org/problem?id=2914
Time Limit: 10000MS | Memory Limit: 65536K | |
Total Submissions: 6407 | Accepted: 2665 | |
Case Time Limit: 5000MS |
Description
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 are M lines, each line contains M integersA, 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 3 0 1 1 1 2 1 2 0 1 4 3 0 1 1 1 2 1 2 3 1 8 14 0 1 1 0 2 1 0 3 1 1 2 1 1 3 1 2 3 1 4 5 1 4 6 1 4 7 1 5 6 1 5 7 1 6 7 1 4 0 1 7 3 1
Sample Output
2 1 2
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 505; const int INF = 1<<30; int map[maxn][maxn]; int Sto_wag(int N){ int dis[maxn],node[maxn],maxj,pre,m,ans=INF; bool visit[maxn]; for(int i = 0; i < N; i ++)node[i] = i; while(N > 1){ m = -1;maxj = 1; for(int i = 1; i < N; i ++){ dis[node[i]] = map[node[0]][node[i]]; visit[node[i]] = 0; if(dis[node[i]] > m){ m = dis[node[i]]; maxj = i; } } pre = 0;visit[node[0]] = 1; for(int j = 1; j < N; j ++){ visit[node[maxj]] = 1; if(j == N-1){ ans = min(ans, m); for(int i = 0; i < N; i ++){ map[node[pre]][node[i]] += map[node[maxj]][node[i]]; map[node[i]][node[pre]] += map[node[maxj]][node[i]]; } node[maxj] = node[--N]; } else{ pre = maxj;m = -1; for(int i = 1; i < N; i ++) if(! visit[node[i]]){ dis[node[i]] += map[node[pre]][node[i]]; if(dis[node[i]] > m){ m = dis[node[i]]; maxj = i; } } } } } return ans; } int main() { int n,m; while(~scanf("%d%d",&n,&m)){ memset(map,0,sizeof(map)); for(int i=0;i<m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); map[a][b]+=c; map[b][a]+=c; } printf("%d\n",Sto_wag(n)); } return 0; }
相关推荐
POJ水题集-----50道左右-----增加自信啊..
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
北大POJ2516-Minimum Cost 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6742534
北大POJ2002-Squares 解题报告+AC代码
poj2516代码最小费用最大流
关于在最小割推荐题目中的源码(包括poj,Hdu两大题库的题目)
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ2305-Basic remains POJ2305-Basic remains
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1321-Chess Problem POJ1321-Chess Problem
用Java代码实现POJ(PKU)上题2494!
POJ3211--Washing Clothes
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
NULL 博文链接:https://128kj.iteye.com/blog/1705139
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
北大POJ1159-Palindrome 解题报告+AC代码
很有用的解题报告。。是acm初级提高的必备资料。。。。。
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码