首页 > 代码库 > BZOJ 2654 tree（二分答案+并查集）
BZOJ 2654 tree（二分答案+并查集）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2654
【题目大意】
给你一个无向带权连通图，每条边是黑色或白色。
让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。
【题解】
我们发现对于选中的边白色是从小到大的，黑色也是从小到大的，
因此我们对所有的白色边加一个权值，那么排序后做mst选取的白色边数量增减性单调，
对于增加的权值进行二分，验证能否满足要求即可。
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int N=100010;struct data{int a,b,u,c;}p[N];bool cmp(data a,data b){return a.u<b.u;}int ans,res,v,e,need,f[N];int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}bool check(int x){ int cnt=0; res=0; for(int i=0;i<v;i++)f[i]=i; for(int i=1;i<=e;i++){if(!p[i].c)p[i].u+=x;} sort(p+1,p+e+1,cmp); for(int i=1;i<=e;i++){if(!p[i].c)p[i].u-=x;} for(int i=1;i<=e;i++){ if(p[i].u<x)continue; if(sf(p[i].a)!=sf(p[i].b)){ res+=p[i].u; f[sf(p[i].a)]=sf(p[i].b); cnt+=(p[i].c==0); } }return cnt>=need;}int main(){ while(~scanf("%d%d%d",&v,&e,&need)){ for(int i=1;i<=e;i++){scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].u,&p[i].c);} int l=-100,r=100; while(l<=r){ int mid=(l+r)>>1; if(check(mid))l=mid+1,ans=res; else r=mid-1; }printf("%d\n",ans); }return 0;}BZOJ 2654 tree（二分答案+并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。