[BZOJ2654]tree 最小生成树+贪心

2654: tree

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 2435 Solved: 1011
[Submit][Status][Discuss]

Description

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

题目保证有解。

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

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

V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

HINT

原数据出错，现已更新 by liutian,但未重测---2016.6.24

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int V,E,need,f;

 struct data {

     int u,v,val,c;

 }e[];

 int fa[];

 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

 bool cmp(data t,data t1){

     return t.c==t1.c?t.val<t1.val:t.c<t1.c;

 }

 int ans=;

 int main() {

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

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

         scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].val,&e[i].c);

     }

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

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

     int sum=;

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

         int x=find(e[i].u),y=find(e[i].v);

         if(x!=y) {

             if(sum>=need){

                 if(e[i].c==) continue;

                 sum++;

                 fa[x]=fa[y];

                 ans+=e[i].val;

             }

             else {

                 ans+=e[i].val;

                 fa[x]=fa[y];

                 sum++;

             }

         }

         if(sum==V-) break;

     }

     printf("%d",ans);

 }

秒客网