BZOJ_1196_[HNOI2006]公路修建问题_kruskal+二分答案
题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1196
分析：
先把所有路都拆成两条。
二分答案mid，把大于mid的边除去，优先加一级公路，判断能不能加进去k条。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 10050
struct A{
int a,b,v;
}e[N<<2];
int n,m,k,fa[N],usex[N<<1],usey[N<<1];
int find(int x){
return fa[x]^x?fa[x]=find(fa[x]):x;
}
bool check(int x){
for(int i=1;i<=n;i++)fa[i]=i;
int ne=0;
for(int i=1;i<=m;i++){
if(e[i].v>x)continue;
int dx=find(e[i].a),dy=find(e[i].b);
if(dx!=dy){
fa[dx]=dy;
ne++;if(ne==n-1)return 1;
}
}if(ne<k)return 0;
for(int i=m+1;i<=2*m;i++){
if(e[i].v>x)continue;
int dx=find(e[i].a),dy=find(e[i].b);
if(dx!=dy){
fa[dx]=dy;ne++;if(ne==n-1)return 1;
}
}return 0;
}
int main(){
scanf("%d%d%d",&n,&k,&m);m--;
int x,y,z,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&x,&y,&z,&w);
e[i].a=e[i+m].a=x;
e[i].b=e[i+m].b=y;
e[i].v=z;e[i+m].v=w;
}
int l=0,r=1<<30;
while(l<r){
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d\n",l);
for(int i=1;i<=n;i++)fa[i]=i;
int ne=0;
for(int i=1;i<=m;i++){
if(e[i].v>l)continue;
int dx=find(e[i].a),dy=find(e[i].b);
if(dx!=dy){
fa[dx]=dy;
ne++;
usex[i]=1;
}
}
for(int i=m+1;i<=m+m;i++){
if(e[i].v>l)continue;
int dx=find(e[i].a),dy=find(e[i].b);
if(dx!=dy){
fa[dx]=dy;
ne++;
usey[i-m]=1;
}
}
for(int i=1;i<=m;i++){
if(usex[i])printf("%d 1\n",i);
else if(usey[i])printf("%d 2\n",i);
}
}