看心情填坑

http://poj.org/problem?id=3228

若干个城镇之间有若干条边相连，每个城镇存在一定容量的金矿或者仓库，或者两者都有或都没有，现在要把所有的金矿运到仓库里，求这样做要使用的最长边长度的最小值

一眼网络流（括弧笑）

实际上就是每个点存在一个权值：仓库容量-金矿容量，我们目标就是要连接若干条边使得每一个联通块总权值>=0，这个东西可以动态加边+并查集很好做，而且效率比网络流不知道好到哪里去了

#include<cstdio>
#include<algorithm>
using namespace std;
int n,sum,x,m;
int a[205],fa[205];;
struct edge{
	int x,y,l;
}e[40005];
bool cmp(edge k1,edge k2){return k1.l<k2.l;}
int find(int k){
	if(fa[k]==k)return k;
	fa[k]=find(fa[k]);
	return fa[k];
}
int main(){
	while(scanf("%d",&n),n){
		sum=0;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			a[i]-=x;
			fa[i]=i;
			if(a[i]>0)sum++;
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].l);
		sort(e+1,e+1+m,cmp);
		int i;
		for(i=1;i<=m;i++){
			int X=find(e[i].x),Y=find(e[i].y);
			if(X!=Y){
				if(a[X]>0)sum--;
				if(a[Y]>0)sum--;
				a[X]+=a[Y];
				fa[Y]=X;
				if(a[X]>0)sum++;
			}
			if(sum==0)break;
		}
		if(sum==0)printf("%d\n",e[i].l);
		else printf("No Solution\n");
	}
}