P2323 [HNOI2006]公路修建问题

five20 2021-08-29 原文

题目描述

输入输出格式

输入格式：

在实际评测时，将只会有m-1行公路

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

Solution：

　　本题贪心+并查集。

　　首先求最大值的最小值，显然需要二分答案，问题就是如何check，对于本题要构造一棵生成树，不一定是最小生成树但必须满足最大值最小，所以我们直接$O(n)$扫一遍所有的边，先把满足c1的限制的边都加入并查集且判断是否至少有k条边，再去判断c2的限制，判断能否形成生成树就好了。

代码：

/*Code by 520 --8.19*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=10005;
int n,m,k,fa[N],ans[N<<1];
struct node {
    int u,v,c1,c2;
}e[N<<1];

int gi(){
    int a=0;char x=getchar();
    while(x<\'0\'||x>\'9\')x=getchar();
    while(x>=\'0\'&&x<=\'9\')a=(a<<3)+(a<<1)+(x^48),x=getchar();
    return a;
}

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

il bool check(int x){
    int tot=0;
    For(i,1,n) fa[i]=i;
    For(i,1,m) if(e[i].c1<=x){
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v) fa[u]=v,tot++;
    }
    if(tot<k)return 0;
    For(i,1,m) if(e[i].c2<=x){
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v) fa[u]=v,tot++;
        if(tot==n-1)return 1;
    }
    return 0;
}

il void print(int x){
    int tot=0;
    For(i,1,n) fa[i]=i;
    For(i,1,m) if(e[i].c1<=x){
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v) fa[u]=v,ans[i]=1,++tot;
        if(tot==n-1)return;
    }
    For(i,1,m) if(e[i].c2<=x){
        int u=find(e[i].u),v=find(e[i].v);
        if(u!=v) fa[u]=v,ans[i]=2,++tot;
        if(tot==n-1)return;
    }
}    

il void init(){
    n=gi(),k=gi(),m=gi()-1;
    int l=0,r=0,pp;
    For(i,1,m) e[i].u=gi(),e[i].v=gi(),e[i].c1=gi(),e[i].c2=gi(),r=max(r,max(e[i].c1,e[i].c2));
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) pp=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",pp),print(pp);
    For(i,1,m) if(ans[i]) printf("%d %d\n",i,ans[i]);
}

int main(){
    init();
    return 0;
}