给你一个无向带权连通图,每条边是黑色或白色。求一棵最小权的恰好有 K 条白色边的生成树。题目保证有解
二分一个增加量md, 给每个白边权值加md , 跑一下kruskal , 看贪心取了多少白边,和K比较检验答案
#include <bits/stdc++.h> using namespace std ; const int N=2e5; #define int long long int n,m,K,tot; int S; int f[N]; struct E{ int x,y,z,col; }a[N]; int cmp(E x,E y){ if(x.z==y.z) return x.col<y.col; return x.z<y.z; } int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } void add(int x,int y,int z,int col){ tot++; a[tot].x=x,a[tot].y=y,a[tot].z=z; a[tot].col=col; } int chk(int md){ S=0; int i,fx,fy,ans=0,cnt=0; for(i=0;i<n;i++) f[i]=i; for(i=1;i<=tot;i++) if(a[i].col==0) a[i].z+=md; sort(a+1,a+1+tot,cmp); for(i=1;i<=tot;i++){ fx=find(a[i].x),fy=find(a[i].y); if(fx!=fy){ S+=a[i].z; if(a[i].col==0) ans++; f[fx]=fy; cnt++; } if(cnt==n-1) break; } for(i=1;i<=tot;i++) if(a[i].col==0) a[i].z-=md; return ans>=K; } main(){ int i,x,y,z,t; cin>>n>>m>>K; for(i=1;i<=m;i++) cin>>x>>y>>z>>t,add(x,y,z,t); int ans=0; int l=-1e4,r=1e4; while(l<=r){ int md=(l+r)/2; if(chk(md)) l=md+1,ans=S-K*md; else r=md-1; } cout<<ans; }
标签:loj,10069,Tree,long,int,3.1 From: https://www.cnblogs.com/towboa/p/16881255.html