记录编号	131294	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] tree(陈立杰)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.959 s
提交时间	2014-10-24 11:12:20	内存使用	2.03 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEN=50010,SIZEM=100010;
class EDGE{
public:
	int a,b;
	int w,c;//边权和颜色
	//0白1黑
};
bool operator < (EDGE s,EDGE t){
	return s.w<t.w;
}
class RESULT{//某次Kruskal的答案
public:
	int cost,white;
};
RESULT res_assign(int a,int b){
	return (RESULT){a,b};
}
class Kruskal_Solver{
public:
	int ufs[SIZEN];
	int grand(int x){
		return !ufs[x]?x:ufs[x]=grand(ufs[x]);
	}
	RESULT calc(int N,int M,EDGE edges[]){//要求edges已排好,返回值为(权值,白边数)
		memset(ufs,0,sizeof(ufs));
		int cost=0,white=0,etot=0;
		for(int i=1;i<=M&&etot<N-1;i++){
			EDGE &e=edges[i];
			int ga=grand(e.a),gb=grand(e.b);
			if(ga==gb) continue;
			cost+=e.w;if(!e.c) white++;etot++;
			ufs[ga]=gb;
		}
		return res_assign(cost,white);
	}
}S;
int N,M,need;
EDGE edges[SIZEM];
vector<EDGE> e0;//白边集合
vector<EDGE> e1;//黑边集合
RESULT F(int x,bool type){//所有白边权值+x,type=0求最少白边数,type=1求最多白边数
	type^=1;
	int p0=0,p1=0;
	for(int i=1;i<=M;i++){
		if(p1>=e1.size()||(p0<e0.size()&&e0[p0].w+x+type<=e1[p1].w)){
			edges[i]=e0[p0++];
			edges[i].w+=x;
		}
		else edges[i]=e1[p1++];
	}
	return S.calc(N,M,edges);
}
void answer(RESULT res,int x){
	printf("%d\n",res.cost-x*need);
}
void work(void){
	int l=-101,r=101;
	RESULT res0,res1;
	while(l<r){
		int mid=floor((l+r)/2.0);//这比较诡异,因为要考虑负数
		res0=F(mid,0),res1=F(mid+1,1);
		if(res0.white>need) l=mid+1;
		else if(res1.white<need) r=mid;
		else{
			RESULT tmp=F(mid,1);
			if(tmp.white>=need) answer(tmp,mid);
			else answer(res1,mid);
			return;
		}
	}
	RESULT tmp=F(l,0);
	answer(tmp,l);
}
void read(void){
	scanf("%d%d%d",&N,&M,&need);
	for(int i=1;i<=M;i++){
		EDGE e;
		scanf("%d%d%d%d",&e.a,&e.b,&e.w,&e.c);
		e.a++,e.b++;
		if(!e.c) e0.push_back(e);
		else e1.push_back(e);
	}
	sort(e0.begin(),e0.end());
	sort(e1.begin(),e1.end());
}
int main(){
	freopen("nt2012_tree.in","r",stdin);
	freopen("nt2012_tree.out","w",stdout);
	read();
	work();
	return 0;
}