61.187.179.132:8080/JudgeOnline/showproblem
看似水题。。其实不是很水（应该是我太菜了囧。。）
之前想了几种算法都是错的。。就不说了。最后的算法是二分最大值。并用并查集帮忙(*^__^*)
然后首先扫描一遍所有的边，能够建一号公路的就建一号公路。扫描的话如果k没达到，就是false
然后再扫描一遍所有的边，把能建的二号公路也建上去。判断一下是否联通的就OK了。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
const int maxn=10000;
int n,k,m;
struct Data
{
int s,t,c1,c2;
void operator()(int _s,int _t,int _c1,int _c2)
{s=_s;t=_t;c1=_c1;c2=_c2;}
}E[maxn*2];
int F[maxn];
int find(int x)
{
if(F[x]==x) return x;
return F[x]=find(F[x]);
}
int Union(int i,int j){F[j]=i;}
bool check(int limit)
{
int cnt=n,r=k;
rep(i,n) F[i]=i;
for(Data*i=E;i!=E+m;i++)
{
if(i->c2<=limit)
{
int a=find(i->s),b=find(i->t);
if(a!=b) Union(a,b),–cnt,–r;
}
}
if(r>0) return false;
for(Data*i=E;i!=E+m;i++)
{
if(i->c1<=limit)
{
int a=find(i->s),b=find(i->t);
if(a!=b) Union(a,b),–cnt;
}
if(cnt==1) return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>k>>m;int s,t,c1,c2;
rep(i,m)
{
scanf("%d %d %d %d",&s,&t,&c2,&c1);
E[i](s-1,t-1,c1,c2);
}
int l=0,r=30000;
while(l+1<r)
{
int m=(l+r)/2;
if(check(m))
r=m;
else
l=m;
}
cout<<r<<endl;
}