首页 > 代码库 > 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]公路修建问题（二分答案+并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。