洛谷3623 [APIO2008]免费道路

Luogu

分析

题意简化后就是:给定一张边权为$0$或$1$的图,求一颗有恰好$k$条$0$边的生成树。

首先,肯定有一些边必须选,不然不会是一颗生成树。

那么先求出最大生成树(优先选$1$边),然后最大生成树里的$0$边就是必须要选的$0$边。

然后把这些必须要选的边加进去,再求一颗生成树,使得正好有$k$条$0$边即可。

无解的情况:必须要选的$0$边数多于$k$、图不连通。

但是这么分析好像很简单的样子

代码

调错调半天结果发现$<$写成$>$ qwq

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

inline int read() {
    R int X=0; R char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) X=X*10+c-'0',c=getchar();
    return X;
}

const int MAXN=20010,MAXM=100010;

struct Union_Find_Set {
    int sz[MAXN],root[MAXN];
    inline void init(const int n) {
        for (R int i=0;i<=n;++i) sz[i]=1,root[i]=i;
    }
    inline int find(const int x) {
        return root[x]==x?x:root[x]=find(root[x]);
    }
    inline void merge(int a,int b) { 
        a=find(a),b=find(b);
        if (a==b) return;
        if (sz[a]>sz[b]) root[b]=a,sz[a]+=sz[b],sz[b]=0;
        else root[a]=b,sz[b]+=sz[a],sz[a]=0;
    }
    inline int check(int a,int b) {
        return find(a)==find(b);
    }
};


struct Edge { int u,v,w; };
Edge e[MAXM];
int ok[MAXM];
Union_Find_Set S;
int n,m,k;

inline int cmp1(const Edge a,const Edge b) { return a.w>b.w; }
inline int cmp2(const Edge a,const Edge b) { return a.w<b.w; }
inline int qwq() {
    int tmp=S.find(1);
    for (R int i=2;i<=n;i++)
        if (S.find(i)!=tmp) return 1;
    return 0;
}

int main() {
    n=read(),m=read(),k=read();
    for (R int i=1;i<=m;++i) e[i].u=read(),e[i].v=read(),e[i].w=read();
    int cnt=0;
    sort(e+1,e+m+1,cmp1); S.init(n);
    for (R int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (S.check(u,v)) continue;
        S.merge(u,v);
        if (!w) ++cnt,e[i].w=-1; //该条鹅卵石路必须选 
    }
    if (cnt>k||qwq()) { puts("no solution"); return 0; }
    sort(e+1,e+m+1,cmp2); S.init(n); cnt=0;
    for (R int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (S.check(u,v)) continue;
        if (w==-1) { ok[i]=1,e[i].w=0,++cnt; S.merge(u,v); } //加进去 
        else if (!w&&cnt<k) { ok[i]=1,++cnt; S.merge(u,v); } //加一条鹅卵石路 
        else if (w==1) { ok[i]=1; S.merge(u,v); }
    }
    if (cnt<k||qwq()) { puts("no solution"); return 0; } //选不到k条
    for (R int i=1;i<=m;++i)
        if (ok[i]) printf("%d %d %d\n",e[i].u,e[i].v,e[i].w);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 30 PM

发表评论