Problem

前往原 OJ 查看。

Solution

最大最小，二分。
怎么验证？
首先尽量把符合条件的一级公路合并。看看数量是否达到了要求。
如果达到了要求，就把所有符合条件的公路合并。看看是否成了一棵生成树。
没了。

以及记住看清题。像我这种没看清题的做这个就比较蛋疼。

// Code by ajcxsu
// Problem: Road

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+10, M=5e4;
struct Edge {
    int f,t,w,ty,idx;
    bool operator < (const Edge &b) {
        return ty!=b.ty?ty<b.ty:w<b.w;
    }
} e[M];
struct Answer {
    int idx,ty;
    bool operator < (const Answer &b) {
        return idx<b.idx;
    }
} nans[M], ans[M];
int p,ap,eap;

int fa[N];
void init() { memset(fa,0,sizeof(fa)); }
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
bool Union(int a,int b) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return false;
    fa[af]=bf;
    return true;
}

int n,k,m;
bool check(int x) {
    init();
    ap=0;
    int cnt=0,i;
    for(i=0;i<p && e[i].ty!=2 && cnt!=n-1; i++) {
        if(e[i].w<=x)
            if(Union(e[i].f, e[i].t)) cnt++, nans[ap].idx=e[i].idx, nans[ap++].ty=e[i].ty;
    }
    if(cnt<k) return false;
    for(;i<p && cnt!=n-1;i++) {
        if(e[i].w<=x)
            if(Union(e[i].f, e[i].t)) cnt++, nans[ap].idx=e[i].idx, nans[ap++].ty=e[i].ty;
    }
    if(cnt==n-1) return true;
    return false;
}

int main() {
    scanf("%d%d%d",&n,&k,&m);
    m--;
    int a,b,c1,c2;
    int l=0,r=0,mid;
    for(int i=0;i<m;i++) {
        scanf("%d%d%d%d",&a,&b,&c1,&c2);
        e[p].f=a, e[p].t=b, e[p].w=c1, e[p].ty=1, e[p].idx=i+1;
        e[p+1]=e[p], e[p+1].w=c2, e[p+1].ty=2, e[p+1].idx=i+1;
        p+=2;
        if(c1>r) r=c1;
        if(c2>r) r=c2;
    }
    sort(e,e+p);
    while(l<r) {
        mid=(l+r)>>1;
        if(check(mid)) memcpy(ans,nans,sizeof(ans)), eap=ap, r=mid;
        else l=mid+1;
    }
    printf("%d\n",r);
    sort(ans,ans+eap);
    for(int i=0;i<eap;i++) printf("%d %d\n",ans[i].idx, ans[i].ty);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_2323.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆