3061764_ac_3965ms_1728k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
#include <algorithm>
using namespace std;

#define initSet(n,Arr) for(int i=0;i<n;++i)Arr[i]=i;
#define MAX 1<<30;
int graph[600][600];

int globalMinCut(int n){

	bool* A=new bool[n];
	int* V=new int[n];
	int* W=new int[n];
	
	initSet(n,V);
	
	int best=MAX;	
	while(n>1){
		int maxj=1;
		
		A[V[0]] = true;		
		for(int i=1; i<n; ++i){
			A[V[i]]=false;
			W[i]=graph[V[0]][V[i]];
			
			if(W[i]>W[maxj])
				maxj=i;
		}
		
		int prev=0,buf=n;
		while(--buf){
			A[V[maxj]]=true;
				
			if(buf==1){
				best=min(best,W[maxj]);
				
				for(int k=0; k<n; ++k)
					graph[V[k]][V[prev]]=(graph[V[prev]][V[k]]
							+=graph[V[maxj]][V[k]]);
				V[maxj]=V[--n];				
			}
			prev=maxj;			
			maxj=-1;
			
			for(int j=1; j<n; ++j)
				if(!A[V[j]]){
					W[j]+=graph[V[prev]][V[j]];
					
					if(maxj<0 || W[j]>W[maxj])
						maxj=j;
				}
		}
	}
	
	delete[] A;
	delete[] V;
	delete[] W;
	return best;
}


int main(){
	int n,m;
	
	while(scanf("%d %d",&n,&m)==2){
		memset(graph,0,sizeof(graph)/sizeof(bool));
		
		int v,w,c;
		
		while(m--){
			scanf("%d %d %d",&v,&w,&c);
			graph[v][w]+=c;
			graph[w][v]+=c;
		}		
		printf("%d\n",globalMinCut(n));
	}
}