BZOJ 1196: [HNOI2006]公路修建问题 – [二分/最小生成树]

题目传送门(BZOJ)
>原文链接<

题解 ：

最大权最小，明显的二分答案特征

考虑二分答案，对于权值小于mid的边，优先满足一级公路。若不足K条则把 l 变大， 若足够则连接二级公路。

由于题目要求必须是 n-1 条边，所以这样一定是正确的。

代码 ：

#include 
#include 
#include 
#include 
using namespace std;
const int N = 11000;
const int M = 22000;
int l,r;
int n,m,k;
int fa[N];
struct node {
    int s,t,v1,v2;
}e[M];
bool cmp(const node &a, const node &b) {
    if(a.v1==b.v1)return a.v2r)r=e[i].v1;
    }
    sort(e+1,e+m,cmp);
}
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool check(int x) {
    for(int i=1;i<=n;i++) {
        fa[i]=i;
    }
    int cnt=0;
    for(int i=1;i<=m;i++) {
        if(e[i].v1>x)continue;
        int dx=find(e[i].s),dy=find(e[i].t);
        if(dx!=dy) {
            fa[dx]=dy;
            cnt++;
        }
    }
    if(cntx)continue;
        int dx=find(e[i].s),dy=find(e[i].t);
        if(dx!=dy) {
            fa[dx]=dy;
            cnt++;
        }
    }
    if(cnt!=n-1)return 0;
    return 1;
}
int main() {
    init();
    int ans;
    while(l<=r) {
        int mid = (l+r) >>1;
        if(check(mid)) {
            ans=mid;
            r = mid-1 ;
        }
        else {
            l = mid +1 ;
        }
    }
    printf("%d\n",ans);
}