Time Limit: 10000MS | Memory Limit: 65536K | |
Total Submissions: 6448 | Accepted: 2686 | |
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 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 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
Source
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int VM=520; const int INF=0x3f3f3f3f; int n,m,mincut,src,des; int map[VM][VM],dis[VM],vis[VM],combine[VM]; void Search(){ //最大生成树 int i,j,k; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); src=des=-1; int tmp; for(i=0;i<n;i++){ tmp=-INF; for(j=0;j<n;j++) if(!combine[j] && !vis[j] && tmp<dis[j]){ k=j; tmp=dis[j]; } if(k==des) return ; src=des; des=k; //最后两个扩展的顶点。 /* printf("---> i=%d k=%d\n",i,k); printf("@@@@@@@@@@@@@@@\n"); for(j=0;j<n;j++) printf("%d ",dis[j]); printf("\n"); printf("@@@@@@@@@@@@@@@\n"); */ mincut=dis[k]; vis[k]=1; for(j=0;j<n;j++) if(!combine[j] && !vis[j]) dis[j]+=map[k][j]; } } int Stoer_Wagner(){ memset(combine,0,sizeof(combine)); int ans=INF; //min=MAXINT,固定一个顶点P for(int i=0;i<n-1;i++){ Search(); //从点P用“类似”prim的s算法扩展出“最大生成树”,记录最后扩展的顶点和最后扩展的边 /* printf("---------------\n"); printf("i=%d : ",i); for(int j=0;j<n;j++) printf("%d ",dis[j]); printf("\n"); printf("---------------\n"); */ ans=min(ans,mincut); //计算最后扩展到的顶点的切割值(即与此顶点相连的所有边权和),若比min小更新min if(ans==0) //图不连通时最小割为0 return 0; combine[des]=1; for(int j=0;j<n;j++) //合并最后扩展的那条边的两个端点为一个顶点 if(!combine[j]){ map[src][j]+=map[des][j]; map[j][src]+=map[j][des]; } } return ans; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ memset(map,0,sizeof(map)); int u,v,w; while(m--){ scanf("%d%d%d",&u,&v,&w); map[u][v]+=w; map[v][u]+=w; } printf("%d\n",Stoer_Wagner()); } return 0; }
相关推荐
poj题目2775文件子目录源代码,递归经典题目,
三道几何题:hdu 1007、hdu 2289、poj 3714
北京大学online judge题号3601,解答及其实验报告
回溯法的模板,关键是回溯的过程,以及在深搜过程中的方向问题
poj 1699的代码和方法说明,个人原创
POJ 3131 双向BFS解立体八数码问题
C + + language learning poj100 question bank and code
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
poj 3310 的代码和方法说明,个人原创
经典的状态DP难题,非常好的的题目,我做了很久才做出来,强烈推荐!!1
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj2516代码最小费用最大流
O(nlogn)凸包问题 poj2187
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
poj的结题报告,里面有一些详细的说明。poj的结题报告,里面有一些详细的说明
部分poj答案分享,其中有部分c和错误案例,很不错哦!
POJ 1170 动态规划。欢迎各种交流讨论。
POJ 北大在线代码判断,参考答案请参考
POJ 2151 Check the difficulty of problems. Practice for dynamic planning.
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了