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 = 3 * 1e5 + 10, inf = 1e9 +10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', 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 = 0;
    for(int i = 1; i <= num; i++) if(e[i].f) ans++;
    return ans;
}
int kruskal(int opt) {
    if(opt == 1) sort(e + 1, e + num + 1);
    else sort(e + 1, e + num + 1, comp);
    for(int i = 1; i <= n; i++) fa[i] = i;
    int cnt = 0;
    if(opt == 2) 
        for(int i = 1; i <= num; i++) 
            if(e[i].f) fa[find(e[i].u)] = find(e[i].v), cnt++;
    for(int i = 1; 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 == 1) {
            if(w == 0) e[i].f = 1;
            if((++cnt) == n - 1) return calc();
        } else if(opt == 2) {
            cnt++; e[i].f = 1;
            if(cnt == k) return 1;
        } else if(opt == 3) {
            if(w == 0 && (!e[i].f)) continue;
            if((++cnt <= n - 1)) printf("%d %d %d\n", x, y, w);
        }
        fa[fx] = fy;
    }
    return 0;
}
int main() {
    n = read(); m = read(); k = read();
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read(), z = read();
        addedge(x, y, z); //addedge(y, x, z);
    }
    if(kruskal(1) > k) {puts("no solution"); return 0;}
    if(!kruskal(2)) {puts("no soltion"); return 0;}
    kruskal(3);
    return 0;
}