题目链接：bzoj2654 题目大意： 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。
题解： 二分+MST 诶呀，题解好机智，，， 如果把所有白色边都减去一个delta后得到一个最小生成树的话，那么可以发现，这个生成树中的白色边是根据delta的增大而不降的，可以说是有单调性的。于是就二分这个delta，每次跑最小生成树check就好了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<iostream> using namespace std; #define maxn 50100 #define maxm 101000 const double inf=20000000; struct node { int x,y,b;double c; }a[maxm]; bool cmp(node x,node y) { if (x.c!=y.c) return x.c<y.c; return x.b<y.b; } int n,m,need,fa[maxn]; int ffind(int x){return (x==fa[x])?x:fa[x]=ffind(fa[x]);} double twdiv(double delta) { int i,cnt=0,num=0;double ans=0; for (i=1;i<=n;i++) fa[i]=i; for (i=1;i<=m;i++) if (!a[i].b) a[i].c-=delta; sort(a+1,a+m+1,cmp); for (i=1;i<=m;i++) { int fx=ffind(a[i].x),fy=ffind(a[i].y); if (fx!=fy) { fa[fx]=fy;cnt++; if (!a[i].b) num++; ans+=a[i].c; if (cnt==n-1) break; } } for (i=1;i<=m;i++) if (!a[i].b) a[i].c+=delta; if (num>=need) return ans; return -inf; } int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int i,x,y,b,c;double ans,det; scanf("%d%d%d",&n,&m,&need); for (i=1;i<=m;i++) { scanf("%d%d%d%d",&x,&y,&c,&b); x++;y++;a[i].x=x;a[i].y=y;a[i].c=c;a[i].b=b; } ans=det=0; double l,r,mid; l=-100;r=100; while (l<r) { mid=(l+r)/2; double now=twdiv(mid); if (now==-inf) l=mid+1; else {r=mid-1;ans=now;det=mid;} } printf("%d\n",(int)(ans+det*need)); return 0; }