考虑先不管限制跑一遍 $Kruscal$
如果白色边少了，说明白边相对权值比较大
如果白色边多了，说明白边相对权值比较小
发现如果给白边适当改变一点权值，就可以使得白边选择的数量改变
考虑二分一个偏移量 $mid$
每次给所有白边加上 $mid$ 后跑一遍 $Kruscal$
看看白边是多了还是少了，如果多了就说明 $mid$ 偏小，如果少了说明 $mid$ 偏大
最后答案别忘了把加上的边权减回来
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,INF=1e9+7; struct edge { int u,v,d,col; inline bool operator < (const edge &tmp) const { return d!=tmp.d ? d<tmp.d : col<tmp.col; } }e[N],tmp[N]; int n,m,K,ans,Res; int fa[N]; inline int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); } inline int calc(int p) { int cnt=0,tot=0; Res=0; //cnt统计已经加了多少边，tot统计加的白边 for(int i=1;i<=m;i++) { tmp[i]=e[i]; if(!e[i].col) tmp[i].d+=p; } for(int i=1;i<=n;i++) fa[i]=i; sort(tmp+1,tmp+m+1); for(int i=1;i<=m;i++) { int u=tmp[i].u,v=tmp[i].v; int fx=find(u),fy=find(v); if(fx==fy) continue; fa[fx]=fy; Res+=tmp[i].d; cnt++; if(!tmp[i].col) tot++; if(cnt==n-1) break; } return tot>=K; } int main() { n=read(),m=read(),K=read(); for(int i=1;i<=m;i++) { e[i].u=read()+1; e[i].v=read()+1; e[i].d=read(); e[i].col=read(); } int L=-100,R=100,mid; while(L<=R) { mid=L+R>>1; if(calc(mid)) L=mid+1,ans=mid; else R=mid-1; } calc(ans); printf("%d",Res-ans*K);//最后答案把加上的边权减回来 return 0; }