记录编号	437453	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] tree(陈立杰)	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	1.168 s
提交时间	2017-08-14 10:23:34	内存使用	4.89 MiB

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 100005
using namespace std;
int v,ei,m,n,zz,s,t,c,col,ans;
int dad[2*maxn];
struct node{
	   int fro,to,next,v,col;
	   bool operator<(node A)const{
	   	    return (v==A.v)?col<A.col:v<A.v;
	   }
}e[2*maxn];
int find(int x){
    if(dad[x]==x) return x;
    return dad[x]=find(dad[x]);
}
int check(int x){ 
	 for(int i=1;i<=ei;i++)
	     if(e[i].col==0) e[i].v+=x;
	 sort(e+1,e+1+ei);
     for(int i=1;i<=v;i++) dad[i]=i;
     int sum=0,tot=0,has=0,ret;
     for(int i=1;i<=ei;i++){
	     int xx=find(e[i].fro);
	     int yy=find(e[i].to);
	     if(xx!=yy){
	        dad[yy]=xx;
	        tot++;
	        has+=1-e[i].col;
	        sum+=e[i].v;
	        if(tot==v-1){
	           if(has>=n) {ans=sum-n*x;ret=true;}
	           else ret=false;
	        }
		}
    }
    for(int i=1;i<=ei;i++)
        if(e[i].col==0) e[i].v-=x;
	return ret;
} 
int main(){
	freopen("nt2012_tree.in","r",stdin);
	freopen("nt2012_tree.out","w",stdout);
	scanf("%d%d%d",&v,&ei,&n);
	int l=0,r=0;
	for(int i=1;i<=ei;i++){
	    scanf("%d%d%d%d",&s,&t,&c,&col);
	    e[i].fro=s+1;
	    e[i].to=t+1;
	    e[i].v=c;
	    e[i].col=col;
	}
	l=-101;r=101;
	while(l<r){
		  //cout<<l<<" "<<r<<endl;
	      int mid=(l+r)>>1;
	      if(check(mid+1)) l=mid+1;
	      else r=mid;
	}printf("%d",ans);
}