BZOJ_1196_[HNOI2006]公路修建问题_kruskal+二分答案

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);

    }

}