A1541 兽径管理

// A1541 兽径管理 —— 增量维护最小生成森林
//
// 每周新增一条兽径，要求输出「目前已知的所有兽径」构成的图的最小生成树权值；
// 若图不连通则输出 -1。
//
// 增量做法：维护当前图的最小生成森林。
//   1) 新兽径的两端属于不同连通块：直接把它加进生成森林，合并两个连通块；
//   2) 两端已经连通：新兽径与树上 u-v 路径构成一个环，
//      环上最重的边一定在 u-v 路径上；若路径上最重的边比新兽径更重，
//      就用新兽径替换它（最小生成树的「换边」性质）。
// 每次只改动一条边，答案立刻更新。

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

const int MAXN = 205;

int n, weeks;
int fa[MAXN];
vector<pair<int, int>> g[MAXN]; // 当前生成森林的邻接表：(邻居, 边权)
int edgeCnt = 0;                // 生成森林的边数
long long total = 0;            // 生成森林的边权和

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

void addEdge(int u, int v, int w) {
    g[u].push_back({v, w});
    g[v].push_back({u, w});
    edgeCnt++;
    total += w;
}

void removeEdge(int u, int v, int w) {
    for (size_t i = 0; i < g[u].size(); i++) {
        if (g[u][i].first == v) {
            g[u].erase(g[u].begin() + i);
            break;
        }
    }
    for (size_t i = 0; i < g[v].size(); i++) {
        if (g[v][i].first == u) {
            g[v].erase(g[v].begin() + i);
            break;
        }
    }
    edgeCnt--;
    total -= w;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> weeks;
    for (int i = 1; i <= n; i++) fa[i] = i;

    for (int week = 1; week <= weeks; week++) {
        int u, v, w;
        cin >> u >> v >> w;

        if (find(u) != find(v)) {
            // 两端不连通：直接连上，生成森林多一条边
            fa[find(u)] = find(v);
            addEdge(u, v, w);
        } else {
            // 两端已连通：在 u-v 路径上找最重的边
            vector<int> par(n + 1, 0), pw(n + 1, 0);
            vector<int> stk;
            stk.push_back(u);
            par[u] = -1;
            while (!stk.empty()) {
                int x = stk.back();
                stk.pop_back();
                for (auto [y, ww] : g[x]) {
                    if (par[y] == 0) {
                        par[y] = x;
                        pw[y] = ww;
                        stk.push_back(y);
                    }
                }
            }
            int mx = -1, child = -1;
            for (int x = v; x != u; x = par[x]) {
                if (pw[x] > mx) {
                    mx = pw[x];
                    child = x;
                }
            }
            if (mx > w) {
                // 环上最重的边在新兽径这一侧：换掉它
                removeEdge(par[child], child, mx);
                addEdge(u, v, w);
            }
        }

        if (edgeCnt == n - 1) {
            cout << total << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
    return 0;
}