POJ3228 并查集或二分最大流枚举答案

忘记写题意了。这题题意：给出每个地点的金矿与金库的数量，再给出边的长度。求取最大可通过边长的最小权值使每个金矿都能运输到金库里。

这题和之前做的两道二分枚举最大流答案的问法很相识，但是这里用最大流速度不够快，所以用了并查集来判断。

方法：边排序后，每次边判断为，将两点合集，若合集中满足金库数量大于金矿数量  则该合集满足条件。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 40000
int n,m,ans,in,out;
int fa[500],f[500];
bool flag;
struct Edge{
int a,b,len;
}edge[MAXN];
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
bool cmp(Edge a,Edge b)
{
return a.len<b.len;
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
int num=0;          //不满足的集合个数
memset(f,0,sizeof(f));
for(int i=0;i<n;i++)
{
scanf("%d",&in);
f[i+1]-=in;
}
for(int i=0;i<n;i++)
{
scanf("%d",&out);
f[i+1]+=out;
if(f[i+1]<0)num++;
}
scanf("%d",&m);
int a,b,c;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[i].a=a;
edge[i].b=b;
edge[i].len=c;
}
sort(edge,edge+m,cmp);
int f1,f2;
for(int i=0;i<=n;i++)
fa[i]=i;
flag=false;
for(int i=0;i<m;i++)  //从小枚举边长  最多40000次
{
f1=find(edge[i].a);
f2=find(edge[i].b);
if(f1!=f2)
{
fa[f1]=f2;   //合并时 进行判断   //f2成为父节点
//以f2为父节点的集合  加上以f1为父节点的结合的f 当此集合满足时
f[f2]+=f[f1];//更新集合若满足条件后  进行操作
if(f[f2]>=0)
{
if(f[f2]-f[f1]<0||f[f1]<0)   //表示解决一个
num--;
}
else if(f[f2]<0)
{
if(f[f2]-f[f1]<0&&f[f1]<0)  //两个问题合并成一个
num--;
}
if(num==0)
{
flag=true;
ans=edge[i].len;
}
}
if(flag)
break;
}
if(flag)
printf("%d\n",ans);
else
printf("No Solution\n");
}
return 0;
}