首页 > 代码库 > BZOJ 1196 [HNOI2006]公路修建问题(二分答案+并查集)

BZOJ 1196 [HNOI2006]公路修建问题(二分答案+并查集)

 

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1196

 

【题目大意】

  对于每条可能维修的公路可选择修一级公路或者二级公路,价值不同

  要求图连通,且至少有k条一级公路时最大价值公路价值最小。

 

【题解】

  二分答案,从一级公路开始处理,利用并查集验证两个条件。

 

【代码】

#include <cstdio>#include <algorithm>using namespace std;const int N=20005;int f[10005],x[N],y[N],c1[N],c2[N],l=1,r=0,ans,n,m,k;int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}bool check(int u){    int k1=0,k2=0;    for(int i=1;i<=n;i++)f[i]=i;    for(int i=1;i<m;i++){        if(c1[i]>u)continue;        int fx=sf(x[i]),fy=sf(y[i]);        if(fx!=fy){            f[fy]=fx;            k1++;        }    }    for(int i=1;i<m;i++){        if(c2[i]>u)continue;        int fx=sf(x[i]),fy=sf(y[i]);        if(fx!=fy){            f[fy]=fx;            k2++;        }    }return (k1>=k&&k1+k2==n-1);}int main(){    scanf("%d%d%d",&n,&k,&m);    for(int i=1;i<m;i++){        scanf("%d%d%d%d",x+i,y+i,c1+i,c2+i);        r=max(c1[i],r); r=max(c2[i],r);    }    while(l<=r){        int mid=(l+r)>>1;        if(check(mid))r=mid-1,ans=mid;        else l=mid+1;    }printf("%d\n",ans);    return 0;}

  

BZOJ 1196 [HNOI2006]公路修建问题(二分答案+并查集)