记录编号	406478	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]公路修建	最终得分	100
用户昵称	不需要黄桃	是否通过	通过
代码语言	C++	运行时间	0.252 s
提交时间	2017-05-18 19:46:55	内存使用	0.96 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct kk
{
	int u,v;
	int wet;
} ed1[23000],ed2[23000];
int n,fath[30002],m,K;
void inii()
{
	for(int i=1;i<=n;i++)
		fath[i]=i;
}
int finn(int x)
{
	int r=x;
	while(r!=fath[r])
		r=fath[r];
	int j,k=x;
	while(k!=fath[k])
	{
		j=fath[k];
		fath[k]=r;
		k=j;
	}
	return r;
}
int comp(const kk &a,const kk &b)
{
	return a.wet<b.wet;
}
void uuin(int x,int y)
{
	int ix=finn(x),iy=finn(y);
	if(ix!=iy)
		fath[ix]=iy;
}
int main()
{
	freopen("hzoi_road.in","r",stdin);
	freopen("hzoi_road.out","w",stdout);
	cin>>n>>K>>m;inii();
	int pp=0,uu,vv,xxam=0;
	for(int j=1;j<=m-1;j++)
	{
		cin>>uu>>vv>>ed1[j].wet>>ed2[j].wet;
		ed1[j].u=uu;ed1[j].v=vv;ed2[j].u=uu;ed2[j].v=vv;
	}
	sort(ed1+1,ed1+m,comp);
	sort(ed2+1,ed2+m,comp);
	int ii=1;
	while(pp<K)
	{
		int qd=finn(ed1[ii].u),zd=finn(ed1[ii].v);
		if(qd!=zd)
		{
			uuin(ed1[ii].u,ed1[ii].v);
			if(xxam<ed1[ii].wet)
				xxam=ed1[ii].wet;
			pp++;
		}
		ii++;
	}
	ii=1;
	while(pp<n-1)
	{
		int qd=finn(ed2[ii].u),zd=finn(ed2[ii].v);
		if(qd!=zd)
		{
			uuin(ed2[ii].u,ed2[ii].v);
			if(xxam<ed2[ii].wet)
				xxam=ed2[ii].wet;
			pp++;
		}
		ii++;
	}
	cout<<xxam;
	return 0;
}