好神奇的一道题
我们发现给白边加上权值后 跑MST后 选到的白边就越少
然后就二分这个加上的权值
不过边界好像有点恶心？不过没关系 思想最重要
#include<bits/stdc++.h> #define N 50005 #define M 100005 using namespace std; struct Edge { int from,to,color,val; }edge[M]; template <class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int n,m,need,ans; int l,r,father[N]; inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } inline bool cmp(const Edge &x,const Edge &y) { if(x.val==y.val) return x.color<y.color; return x.val<y.val; } inline bool check(int del) { for(int i=1;i<=m;i++) if(edge[i].color==0) edge[i].val+=del; for(int i=1;i<=n;i++) father[i]=i; sort(edge+1,edge+m+1,cmp); int white=0,sum=0,cnt=0,flag; for(int i=1;i<=m;i++) { int fx=getfather(edge[i].from),fy=getfather(edge[i].to); if(fx!=fy) { father[fx]=fy; sum+=edge[i].val; cnt++; if(edge[i].color==0) white++; if(cnt==n-1) { if(white>=need) ans=sum-del*need,flag=1; else flag=0; break; } } } for(int i=1;i<=m;i++) if(edge[i].color==0) edge[i].val-=del; return flag; } int main() { read(n); read(m); read(need); for(int i=1;i<=m;i++) { read(edge[i].from); read(edge[i].to); edge[i].from++; edge[i].to++; read(edge[i].val); read(edge[i].color); r=max(r,edge[i].val+1); } l=-r; while(l<r) { int mid=(l+r)/2; if(check(mid)) l=mid+1; else r=mid; } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9848734.html
