题目链接
题目大意：给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。
题解：容易发现，最小生成树中的白边数目随着白边边权增大而减少。二分一个x，给每条白边都加x，就可以愉快的搞了。为了使二分进行下去，条件是白边数>=need即可。当然，有可能一直二分到最后也不会出现恰好有k条白边的情况，但题目保证有解，这样其实是有很多权相等的黑白边，不用处理
我的收获：强啊
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int M=100005; int n,m,k,tot,cnt; int f[M]; struct edge{int u,v,w,c;}e[M*2]; 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*10+ch-'0';ch=getchar();} return x*f; } int fd(int x){return f[x]==x?x:f[x]=fd(f[x]);} bool cmp(edge a,edge b){return a.w<b.w||(a.w==b.w&&a.c<b.c);} bool check(int x) { tot=cnt=0; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) if(!e[i].c) e[i].w+=x; sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++) { int p=fd(e[i].u),q=fd(e[i].v); if(p!=q){ f[p]=q;tot+=e[i].w; if(!e[i].c) cnt++; } } for(int i=1;i<=m;i++) if(!e[i].c) e[i].w-=x; return cnt>=k; } void init() { n=read();m=read();k=read(); for(int i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].c=read(),e[i].u++,e[i].v++; } void work() { int sumv,l=-105,r=105; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) l=mid+1,sumv=tot-k*mid; else r=mid-1; } printf("%d",sumv); } int main() { init(); work(); return 0; }