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;
}
评论 (0)
