1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define MAXN 50010 5 #define MAXM 100010 6 int father[MAXN],n,m,cnt,ans1,ans,need,u[MAXM],v[MAXM],val[MAXM]; 7 bool col[MAXM]; 8 struct node 9 {10     int u,v,val;11     bool col;12 }edge[MAXM];13 void add(int a,int b,int c,int d,int i)14 {15     edge[i].u=a;16     edge[i].v=b;17     edge[i].val=c;18     edge[i].col=d;19 }20 int cmp(node a,node b)21 {22     return a.val==b.val?a.col<b.col:a.val<b.val;//排序时尽量把白边排在前面 23 }24 int find(int x)25 {26     if(father[x]==x)return x;27     else return father[x]=find(father[x]); 28 }29 bool Kruskal(int x)30 {31     ans1=cnt=0;//ans1为最小生成树权值和，cnt为所选白边数目 32     for(int i=1;i<=n;i++)father[i]=i;33     for(int i=1;i<=m;i++)34     {35         add(u[i],v[i],val[i],col[i],i);36         if(!edge[i].col)edge[i].val+=x;37     }38     sort(edge+1,edge+m+1,cmp);39     for(int i=1;i<=m;i++)40     {41         int a=find(edge[i].u);42         int b=find(edge[i].v);43         if(a==b)continue;44         else45         {46             father[b]=a;47             ans1+=edge[i].val;48             if(!edge[i].col)cnt++;49         }50     }51     return cnt>=need;52 }53 int main()54 {55     scanf("%d%d%d",&n,&m,&need);56     for(int i=1;i<=m;i++)scanf("%d%d%d%d",&u[i],&v[i],&val[i],&col[i]);57     int l=-100,r=100;58     while(l<=r)59     {60         int mid=(l+r)/2;61         if(Kruskal(mid))62         {63             l=mid+1;64             ans=ans1-mid*cnt;//总权值减去多加上的白边边权 65         }66         else r=mid-1;67     }68     printf("%d",ans);69     return 0;70 }