首页 > > 程序设计 > C/C++ >

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

2018-09-19 02:44:40来源：博客园阅读 ()

题意

题目链接

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;
}