记录编号	473624	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]公路修建2	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.658 s
提交时间	2017-11-08 20:38:53	内存使用	3.75 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int M=100010;

int n,m,k,tot,ans;
int fa[M];
struct DATE{int fr,to,c1,c2;}date[M<<1];

inline bool cmp1(DATE a,DATE b) { return a.c1<b.c1; }

inline bool cmp2(DATE a,DATE b) { return a.c2<b.c2; } 

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1;ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar(); }
	return x*f;
}

inline int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]); 
}

int main(){

	freopen("hzoi_road2.in","r",stdin);
	freopen("hzoi_road2.out","w",stdout);

	n=read(); k=read(); m=read();			
	for(int i=1;i<m;++i) date[i]=(DATE){read(),read(),read(),read()};
	for(int i=1;i<=n;++i) fa[i]=i;

	sort(date+1,date+m+1,cmp1);

	for(int i=1;i<=k;++i){
		int u=date[i].fr,v=date[i].to;
		int fx=find(u),fy=find(v);
		if(fx==fy) continue;
 		fa[fx]=fy; ++tot;
 		ans=max(ans,date[i].c1);
	}	k=n-1-tot; tot=0;

	sort(date+1,date+m+1,cmp2);

	for(int i=1;i<=m;++i){
		if(tot==k) break;
		int u=date[i].fr,v=date[i].to;
		int fx=find(u),fy=find(v);
		if(fx==fy) continue;
 		fa[fx]=fy; ++tot;
 		ans=max(ans,date[i].c2);
	}	printf("%d\n",ans);

	return 0;

}