记录编号	437274	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] tree(陈立杰)	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	1.100 s
提交时间	2017-08-13 21:33:04	内存使用	1.12 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
	int s=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') {
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
int V,E,need,mid,tmp,cnt;
struct node {
	int fr,to,vv,col;
	friend bool operator <(node a,node b) {
		return (a.vv+(a.col^1)*mid==b.vv+(b.col^1)*mid)?(a.col<b.col):(a.vv+(a.col^1)*mid<b.vv+(b.col^1)*mid);
	}
} edge[100005];
int fa[50005];
int find(int x) {
	return fa[x]!=-1?(fa[x]=find(fa[x])):(x);
}
int kruskal() {
	tmp=cnt=0;
	int k=0;
	memset(fa,-1,sizeof(fa));
	sort(edge+1,edge+E+1);
	for(int i=1; i<=E; ++i) {
		int x=find(edge[i].fr),y=find(edge[i].to);
		if(x!=y) {
			k+=edge[i].col^1;
			fa[x]=y;
			++cnt;
			tmp+=edge[i].vv+mid*(edge[i].col^1);
			if(cnt==V-1) {
				return k;
			}
		}
	}
}
int Main(){
	freopen("nt2012_tree.in","r",stdin);
	freopen("nt2012_tree.out","w",stdout);
	V=read(),E=read(),need=read();
	for(int x,y,z,c,i=1; i<=E; ++i) {
		edge[i]=(node) {
			x=read(),y=read(),z=read(),c=read()
		};
	}
	int l=-100,r=100;
	int ans=0;
	while(l<=r) {
		mid=l+r>>1;
		if(kruskal()>=need) {
			l=mid+1,ans=tmp-mid*need;
		} else {
			r=mid-1;
		}
	}
	printf("%d\n",ans);
	return 0;
}
int hehe=Main();
int main() {
	
}