BZOJ3624: [Apio2008]免费道路(最小生成树)

题意

题目链接

Sol

首先答案一定是一棵树

这棵树上有一些0边是必须要选的，我们先把他们找出来，如果数量$\geqslant k$显然无解

再考虑继续往里面加0的边，判断能否加到k条即可

具体做法是：

先让1在前做生成树，其中加入的0边是必须要选的

再让0边在前做生成树，这时候我们不必考虑最后能否生成一棵树，只需要考虑能否加入k条即可

我的思路：首先必选的0边是一定要统计出来的，然后一次性把剩下的所有0边都加进去，显然其中会有很多没有用，如果加入的边数量$<k$则无解，

否则考虑删除一些0边，LCT维护形成环后每个环上0边的数量，如果环上0的数量$>0$则减一，把该1边加入，否则不加入。如果总的0边数量为k，

直接不断加剩下的边，最后判断能否形成一棵树，否则0边的数量>k，证明无解。

应该是对的吧，不过打死我也不会去写的。。。。。

#include<cstdio>

#include<algorithm>

#define LL long long

using namespace std;

const int MAXN =  * 1e5 + , INF = 1e9 +;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M, K, num, mt, fa[MAXN];

struct Edge {

    int u, v, w, f;

    bool operator < (const Edge &rhs) const {return w > rhs.w;}

}E[MAXN];

void AddEdge(int x, int y, int z) {E[++num] = (Edge) {x, y, z};}

int comp(const Edge &a, const Edge &b) {return a.w < b.w;}

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

int calc() {

    int ans = ;

    for(int i = ; i <= num; i++) if(E[i].f) ans++;

    return ans;

}

int Kruskal(int opt) {

    if(opt == ) sort(E + , E + num + );

    else sort(E + , E + num + , comp);

    for(int i = ; i <= N; i++) fa[i] = i;

    int cnt = ;

    if(opt == )

        for(int i = ; i <= num; i++)

            if(E[i].f) fa[find(E[i].u)] = find(E[i].v), cnt++;

    for(int i = ; i <= num; i++) {

        int x = E[i].u, y = E[i].v, w = E[i].w;

        int fx = find(x), fy = find(y);

        if(fx == fy) continue;

        if(opt == ) {

            if(w == ) E[i].f = ;

            if((++cnt) == N - ) return calc();

        } else if(opt == ) {

            cnt++; E[i].f = ;

            if(cnt == K) return ;

        } else if(opt == ) {

            if(w ==  && (!E[i].f)) continue;

            if((++cnt <= N - )) printf("%d %d %d\n", x, y, w);

        }

        fa[fx] = fy;

    }

    return ;

}

int main() {

    N = read(); M = read(); K = read();

    for(int i = ; i <= M; i++) {

        int x = read(), y = read(), z = read();

        AddEdge(x, y, z); //AddEdge(y, x, z);

    }

    if(Kruskal() > K) {puts("no solution"); return ;}

    if(!Kruskal()) {puts("no soltion"); return ;}

    Kruskal();

    return ;

}

巴特西

BZOJ3624: [Apio2008]免费道路(最小生成树)

题意

Sol

最新文章

热门文章