BZOJ3624：[APIO2008]免费道路

浅谈并查集：https://www.cnblogs.com/AKMer/p/10360090.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3624

题目要求的就是恰好包含\(k\)条鹅卵石路的生成树。

首先我们用水泥边建出生成树森林，然后再用鹅卵石边把森林连成一棵树。

如果需要用到的鹅卵石边大于\(k\)则无解。

如果无法连成一棵树则无解。

连成一棵树之后也许此时用到的鹅卵石边比\(k\)要小，我们暂且称已经用到的鹅卵石边为必要边。

我们把树全部拆掉，然后把必要边连上，在看看能不能把不足的\(k\)条鹅卵石边补上，补得上就有解，否则无解。

剩下的用水泥边填上即可。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n+m)\)

代码如下：

#include <cstdio>
using namespace std;

const int maxn=2e4+5,maxm=1e5+5;

int fa[maxn];bool bo[maxm];
int n,m,k,cnt1,cnt2,cnt,tot;

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

struct road {
    int a,b;

    road() {}

    road(int _a,int _b) {
        a=_a,b=_b;
    }
}cob[maxm],cem[maxm],ans[maxn];

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

int main() {
    tot=n=read(),m=read(),k=read();
    for(int i=1;i<=m;i++) {
        int a=read(),b=read(),opt=read();
        if(opt)cem[++cnt1]=road(a,b);
        else cob[++cnt2]=road(a,b);
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=cnt1;i++) {
        int p=find(cem[i].a),q=find(cem[i].b);
        if(p==q)continue;
        fa[p]=q,tot--;
    }
    if(tot-1>k) {puts("no solution");return 0;}
    for(int i=1;i<=cnt2;i++) {
        int p=find(cob[i].a),q=find(cob[i].b);
        if(p==q)continue;
        fa[p]=q,tot--,bo[i]=1;
    }
    if(tot!=1) {puts("no solution");return 0;}
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=cnt2;i++)
        if(bo[i]) {
            ans[++cnt]=cob[i];
            int p=find(cob[i].a),q=find(cob[i].b);
            fa[p]=q;k--;
        }
    for(int i=1;i<=cnt2&&k;i++)
        if(!bo[i]) {
            int p=find(cob[i].a),q=find(cob[i].b);
            if(p==q)continue;
            fa[p]=q,k--;ans[++cnt]=cob[i];
        }
    if(k) {puts("no solution");return 0;}
    for(int i=1;i<=cnt;i++)
        printf("%d %d 0\n",ans[i].a,ans[i].b);
    for(int i=1;i<=cnt1;i++) {
        int p=find(cem[i].a),q=find(cem[i].b);
        if(p==q)continue;
        printf("%d %d 1\n",cem[i].a,cem[i].b);
        fa[p]=q;
    }
    return 0;
}

BZOJ3624：[APIO2008]免费道路

原文：https://www.cnblogs.com/AKMer/p/10366913.html