参考链接：http://www.cnblogs.com/jiaohuang/archive/2010/11/13/1876418.html
题意：地图上某些点有金子，有些点有房子，还有一些带权路径，问把所有金子运到房子里所要经过最小的最大相邻路是多少。
也就是如果光用比“最小的最大相邻路”那条路更小的路是无法运完所有金子的，那么可以先对路径排序，然后一条一条取， 看看是否满足条件：即是否所有并查集的根节点的权值f[i]为非负。
思路：首先想到的是，要能运完所有的金子，那么必须任意一个连通器中的储藏室的总容量V大于等于所含有的金子的总量C，也就是V-C>=0。那么就想到用一个数组存储该镇的状态，若是储藏室，则权值为储藏的 量；若为发现金子的地方，则权值为金子的量的负值。这样每次合并的时候，都要更新一下父节点，即父节点的权值要加上子节点的权值。最后根节点的权值即为该集合中V-C的值。
若根节点的权值为非负，表明该点集中，可以储存宝藏的容量大于等于发现的宝藏，即这个点集能满足要求。
若根节点的权值为负值，表明该点集中还有一定数量的宝藏需要储存，但是该集合已经没有房间能存储下了，即不能满足条件。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
const int maxn=;
int n,m;
int father[maxn],f[maxn]; //f[i]表示第i个镇所拥有的宝藏，如果为负值，表明此镇需要运出-f[i]的宝藏。如果为正值，表明可以储存f[i]的宝藏
int ans;
struct Edge {
int u,v,w; //u、v是边的两端点，w是边的权值
bool operator<(const Edge tmp) const{
return w<tmp.w;
}
} edge[]; void init(){
for(int i=;i<=n;i++){
father[i]=i;
f[i]=;
}
}
int find_root(int x) {
if(father[x]!=x){
father[x]=find_root(father[x]);
}
return father[x];
}
void Union(int x,int y){
father[y]=x;
}
//判断是否所有集合都满足根节点的权值大于等于0
bool ok(){
int flag=;
for(int i=;i<=n;i++){
if(father[i]==i && f[i]<){
flag=;
break;
}
}
if(flag)
return true;
else
return false;
}
int main() {
int store;
while(scanf("%d",&n)!=EOF) {
if(n==)
break;
init();
for(int i=; i<=n; i++) {
scanf("%d",&store);
f[i]-=store; //需要运出的宝藏
}
for(int i=; i<=n; i++) {
scanf("%d",&store);
f[i]+=store; //可以储存的宝藏，因为发现宝藏和储存宝藏的地方可能为同一个，所以这里累加就行
}
scanf("%d",&m);
for(int i=; i<=m; i++) {
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
} sort(edge+,edge+m+);
int u,v,i=;
//从最小的边开始取
while(i<=m) {
u=edge[i].u;
v=edge[i].v;
int x=find_root(u);
int y=find_root(v);
if(x!=y){
Union(x,y);
f[x]+=f[y];
if(ok()){
ans=i;
break;
}
}
i++;
}
if(i==m+){
printf("No Solution\n");
}
else{
printf("%d\n",edge[ans].w);
} }
return ;
}