【BZOJ 2654】tree

Description

　　给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
　　题目保证有解。

Input

　　第一行V,E,need分别表示点数，边数和需要的白色边数。
　　接下来E行
　　每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

　　一行表示所求生成树的边权和。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

HINT

数据规模和约定

　　0:V<=10

　　1,2,3:V<=15

　　0,..,19:V<=50000,E<=100000

　　所有数据边权为[1,100]中的正整数。

orz 王梦迪大神

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N=;

 struct ee{int x,y,w,c;}e[N*];

 int fa[N];

 int ans,E,V,need,tot;

 int root(int x){

     if(fa[x]==x) return x;

     fa[x]=root(fa[x]);return fa[x];

 }

 bool cmp(ee a,ee b){

     if(a.w==b.w) return a.c<b.c;

     return a.w<b.w;

 }

 int kls(){

     tot=;int sum=,num=;

     for(int i=;i<V;i++) fa[i]=i;

     for(int i=;i<=E&&sum<V-;i++){

         int xx=root(e[i].x),yy=root(e[i].y);

         if(xx!=yy) fa[xx]=yy,sum++,tot+=e[i].w,num+=(e[i].c==);

     }

     return num;

 }

 int main(){

     scanf("%d%d%d",&V,&E,&need);

     int s,t,w,c;

     for (int i=;i<=E;i++){

         scanf("%d%d%d%d",&s,&t,&w,&c);

         e[i].x=s;e[i].y=t;e[i].w=w;e[i].c=c;

     }

     int l=-,r=;

     while(l<=r){

         int mid=(l+r)>>;

         for (int i=;i<=E;i++) if(e[i].c==)e[i].w+=mid;

         sort(e+,e++E,cmp);

         int h=kls();

         if(h>=need) ans=(tot-need*mid),l=mid+;else r=mid-;

     //ans这里要注意一下，1wa

         for (int i=;i<=E;i++) if(e[i].c==)e[i].w-=mid;

     }

     printf("%d",ans);

 }

秒客网