题目描述
输入输出格式
输入格式：
在实际评测时，将只会有m-1行公路
输出格式：
输入输出样例
输入样例#1：
4 2 5
1 2 6 5
1 3 3 1
2 3 9 4
2 4 6 1
3 4 4 2
输出样例#1：
4
2 1
3 2
5 1
输入样例#2：
4 1 5
1 2 6 5
1 3 3 1
2 3 9 4
2 4 6 1
3 4 4 3
输出样例#2：
3
2 1
4 2
5 2
坑到炸的一句话、。。
二分+kruskal
#include <algorithm>
#include <cstdio>
#define N 20005 using namespace std;
struct Edge
{
int x,y,z,id;
bool operator<(Edge a)const
{
return z<a.z;
}
}e1[N],e2[N];
struct node
{
int a,b;
bool operator<(node x)const
{
return a<x.a;
}
}ans[N];
int n,k,m,siz,fa[N];
int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);}
bool check(int x)
{
for(int i=;i<=n;++i) fa[i]=i;
int num=;
for(int i=;i<=m;++i)
{
if(e1[i].z>x) continue;
int fx=find_(e1[i].x),fy=find_(e1[i].y);
if(fx!=fy)
{
num++;
fa[fy]=fx;
}
}
if(num<k) return false;
for(int i=;i<=m;++i)
{
if(e2[i].z>x) continue;
int fx=find_(e2[i].x),fy=find_(e2[i].y);
if(fx!=fy)
{
fa[fy]=fx;
num++;
}
}
if(num==n-) return true;
return false;
}
void get(int x)
{
for(int i=;i<=n;++i) fa[i]=i;
for(int i=;i<=m;++i)
{
if(e1[i].z>x) continue;
int fx=find_(e1[i].x),fy=find_(e1[i].y);
if(fx!=fy)
{
siz++;
fa[fy]=fx;
ans[siz].a=e1[i].id;
ans[siz].b=;
}
}
for(int i=;i<=m;++i)
{
if(e2[i].z>x) continue;
int fx=find_(e2[i].x),fy=find_(e2[i].y);
if(fx!=fy)
{
siz++;
fa[fy]=fx;
ans[siz].a=e2[i].id;
ans[siz].b=;
}
}
}
int main(int argc,char *argv[])
{
scanf("%d%d%d",&n,&k,&m);
int l=,r=,anss;
for(int u,v,w1,w2,i=;i<=m;++i)
{
scanf("%d%d%d%d",&u,&v,&w1,&w2);
e1[i]=(Edge){u,v,w1,i};
e2[i]=(Edge){u,v,w2,i};
r=max(r,w1);
}
sort(e1+,e1+m);
sort(e2+,e2+m);
for(int mid;l<=r;)
{
mid=(l+r)>>;
if(check(mid))
anss=mid,r=mid-;
else l=mid+;
}
printf("%d\n",anss);
get(anss);
sort(ans+,ans++siz);
for(int i=;i<=siz;++i) printf("%d %d\n",ans[i].a,ans[i].b);
return ;
}