HDU - 3002 King of Destruction(全局最小割)

King of Destruction

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1545 Accepted Submission(s): 643

Problem Description
Zhou xingxing is the successor of one style of kung fu called “Karate Kid”.he is falling love with a beautiful judo student,after being humiliated by her boyfriend,a Taekwando master from Japan,Zhou is going to fight with his rival in love.The way they fight is to destroy the wooden plank between some wooden pegs,in order to cut these wooden pegs into two disconnected parts,and destroy each piece of plank need consume different energy.However Zhou xingxing is beginner after all,so he is turn to you for help,please calculate the minimum energy he need to destroy the wooden plank.

Input
The input consists of multiple test cases.
Each test case starts with two integers n (0 < n <= 100) and m in one line, where n、m are the number of wooden pegs and wooden plank.
Following are m lines, each line contains three integers s, e and q (0 <= s, e < n,q > 0), meaning that there need q energy to destroy the wooden plank between s and e.

Output
There is only one line for each test case, which contains the minimum energy they need to complete this fight.

Sample Input
2 1
0 1 50
3 2
0 1 50
1 2 10

Sample Output
50
10

Source
2009 Multi-University Training Contest 11 - Host by HRBEU

Recommend
gaojie | We have carefully selected several similar problems for you: 3001 3004 3007 3003 3000

无向图全局最小割的模板题。

求全局最小割，相当于是在一直用最大生成树缩点。然后当只有两个点的时候，之间权值就是全局最小割。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
const int N=110,inf=0x3f3f3f3f;
using namespace std;
int g[N][N],vis[N],d[N],com[N],s,t,mi,n,m;
void prim(){
	memset(vis,0,sizeof vis);	memset(d,0,sizeof d); s=t=-1;	int id;
	for(int i=0;i<n;i++){
		int mx=-inf;
		for(int j=0;j<n;j++)	if(!com[j]&&!vis[j]&&d[j]>mx)	id=j,mx=d[j];
		if(t==id)	return ;
		s=t; t=id;	mi=mx;	vis[id]=1;
		for(int j=0;j<n;j++)	if(!com[j]&&!vis[j])	d[j]+=g[id][j];
	}
}
inline int sw(){
	memset(com,0,sizeof com); int res=inf;
	for(int i=0;i<n-1;i++){
		prim();
		if(mi<res)	res=mi;
		if(res==0)	return 0;
		com[t]=1;
		for(int j=0;j<n;j++){
			if(!com[j]){
				g[s][j]+=g[t][j];	g[j][s]+=g[j][t];
			}
		}
	}
	return res;
}
signed main(){
	while(~scanf("%d %d",&n,&m)){
		memset(g,0,sizeof g);
		while(m--){
			int a,b,c;	scanf("%d %d %d",&a,&b,&c);
			g[a][b]+=c; g[b][a]+=c;
		}
		printf("%d\n",sw());
	}
	return 0;
}