记录编号	130862	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] tree(陈立杰)	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	4.451 s
提交时间	2014-10-23 14:45:48	内存使用	6.58 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 100000000
using namespace std;
int n,m,need,father[50100]={0};
struct node{
	int s,t,v,color;
}E[200010],V[200010];
bool cmp(const node &a,const node &b){return a.v<b.v;}
int find(int x){
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x];
}
void unionn(int x,int y){
	int r1=find(x);
	int r2=find(y);
	if(r1!=r2) father[r2]=r1;
}
int F(int x,int& totv){
	for(int i=1;i<=m;++i){
		V[i]=E[i];
		if(V[i].color==0) V[i].v+=x;
	}
	sort(V+1,V+m+1,cmp);
	for(int i=0;i<n;++i) father[i]=i;
	int ans=0;
	for(int i=1;i<=m;i++){
		if(find(V[i].s)!=find(V[i].t)){
			unionn(V[i].s,V[i].t);
			totv+=V[i].v;
			if(V[i].color==0) ans++;
		}
	}
	return ans;
}
int main(){
	freopen("nt2012_tree.in","r",stdin);
	freopen("nt2012_tree.out","w",stdout);
	scanf("%d%d%d",&n,&m,&need);
	for(int i=1;i<=m;++i) scanf("%d%d%d%d",&E[i].s,&E[i].t,&E[i].v,&E[i].color);
	int l=-101,r=101,t,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		t=F(mid,ans=0);
		if(t>=need) l=mid+1;
		else r=mid-1;
	}
	int last=F(m-10,ans=0);
	int total=-INF;
	for(int i=l-9;i<=r+10;i++){
		t=F(i,ans=0);
		if(last>=need && need>=t){
			t=F(i-1,ans=0);
			if(ans-(i-1)*need>total) total=ans-(i-1)*need;
		}
		last=t;
	}
	printf("%d\n",total);
	return 0;
}