【bzoj1083】[SCOI2005]繁忙的都市

2015.06.11 11:10 Thu | 18次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定一个边权图,求边权最小为多少时图联通……
水题不多说,二分+kruskal

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 305
using namespace std;
struct edge{
    int u,v,c;
}e[100000];
int n,m;
bool cmp(const edge &a,const edge &b)
{
    return a.c<b.c;
}
int fa[N];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool check(int mid)
{
    for(int i=1;i<=n;i++) fa[i]=i;
    int cnt=0;
    for(int i=1;i<=m&&e[i].c<=mid;i++)
    {
        int p=find(e[i].u),q=find(e[i].v);
        if(p==q) continue;
        fa[p]=q;cnt++;
        if(cnt==n-1) break;
    }
    return cnt==n-1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
    sort(e+1,e+m+1,cmp);
    int l=1,r=10000,mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<n-1<<" "<<ans<<endl;
}```