Luogu 兽径管理

题解

解

数组开小没察觉，挂掉好几遍

题意肯定是求最小生成树了，问题在于怎样减少时间消耗。

主要思路是逆序求解，因为这样可以尽可能地减少使用Kruskal的次数，时间复杂度自然就降下来了

每次Kruskal记录用到的边，如果(每一周)删掉了一条用到的边，那自然需要重新求一遍最小生成树；如果没用到，那就不用求了，直接赋值为上一个结果。

如果有一周出现了-1，那它继续删边肯定更不联通了，所以之后所有答案都是-1，break就好

Code

#include <bits/stdc++.h>
const int N = 210;
const int M = 6010;
long long Answer[M];
int fa[N], n, m, nowid;
struct Node {
    int u, v, w, day;
    bool operator < (const Node &a) const {
        return w < a.w;
    }
} E[M << 1]; 
bool Be_use[M << 1];
#define gc getchar()
inline int read() {
    int x = 0, f = 1; char c = gc;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x * f;
}
int Get_fa(int x) {return x == fa[x] ? x : fa[x] = Get_fa(fa[x]);}
long long Work() {
    memset(Be_use, 0, sizeof Be_use);
    for(int i = 1; i <= n; i ++) fa[i] = i;
    long long js(0), ret(0);
    for(int i = 1; i <= m; i ++) {
        if(E[i].day > nowid) continue ;
        int a = E[i].u, b = E[i].v, fa_a = Get_fa(a), fa_b = Get_fa(b);
        if(fa_a != fa_b) js ++, ret += E[i].w, fa[fa_a] = fa_b, Be_use[E[i].day]= 1;
        if(js == n - 1) break;
    }
    if(js != n - 1) return -1;
    return ret;
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; i ++) E[i].u = read(), E[i].v = read(), E[i].w = read(), E[i].day = i;
    std:: sort(E + 1, E + m + 1);
    nowid = m;
    Answer[m] = Work();
    for(int i = m - 1; i >= 1; i --) {
        if(Be_use[i + 1]) nowid = i, Answer[i] = Work();
        else Answer[i] = Answer[i + 1];
        if(Answer[i] == -1) {
            for(int j = 1; j < i; j ++) Answer[j] = -1;
            break;
        }
    }
    for(int i = 1; i <= m; i ++) std:: cout << Answer[i] << "\n";
    return 0;
}