洛谷 P2820 局域网

// P2820 局域网 —— ★ 这一版就能 AC
//
// ★ 关键的一步是一句话的换算：「**删掉的最大**」= 总权和 − 「**留下的最小**」。
//   题目要求删完之后「没有回路」＋「不改变连通性」⇒ 留下的恰好是一片**生成森林**；
//   要删的最大，就让留下的最小 ⇒ 留下的是**最小生成森林**。
//
// ⚠⚠ 两处必须留神：
//   ① 题面**没有保证图是连通的**（它说的是「不改变原图节点的连通性」）——
//      所以这里求的是**森林**不是树，Kruskal 一路收到底、不能要求「收够 n − 1 条」。
//   ② 题面**一个字都没给 k 的上限**（只给了 `1 ≤ n ≤ 100` 和 `1 ≤ f ≤ 1000`）
//      ⇒ 别按 n(n−1)/2 开死数组，用 vector 一路 push 就完了。

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

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

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

    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> e(k);
    long long total = 0;
    for (auto& t : e) {
        cin >> t[1] >> t[2] >> t[0];                  // 读进来是 i j m，存成 (m, i, j)
        total += t[0];                                // ★ 总权和要把**每一条**边都算上
    }

    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long keep = 0;
    for (auto& t : e) {                               // ⚠ 一路收到底，不数够不够 n − 1 条
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        keep += t[0];
    }

    cout << total - keep << '\n';
    return 0;
}

// ★ P2820 的另一条路：从**大**到小扫，能删就删 —— 它也对
//
// 想法比换算更直白：把网线按畅通程度**从大到小**排，
// 一条一条问「拆了它之后，两头还连得上吗？」连得上就拆。
//
// ★ 它给出的答案和正解**逐组相同**（见本页第 ② 步，四档共 1200 组一个不差），
//   理由也是一句话：拆完之后留下的仍然是一片生成森林，
//   而「每次拆最贵的可拆边」正是 Kruskal 的**逆过程**（反向 Kruskal）。
// ⚠ 代价是它每问一次都要跑一遍连通性检查 —— O(k × (n + k))，
//   而正解是一次排序加一遍并查集。这道题 n ≤ 100 无所谓，规模一大就不行了。

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

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

    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> e(k);
    long long total = 0;
    for (auto& t : e) { cin >> t[1] >> t[2] >> t[0]; total += t[0]; }

    sort(e.begin(), e.end(), greater<array<int, 3>>());   // 从大到小
    vector<char> dead(k, 0);

    /* 只用剩下的边，看 a 和 b 还连不连得上 */
    auto connected = [&](int a, int b) {
        vector<int> fa(n + 1);
        for (int i = 1; i <= n; i++) fa[i] = i;
        function<int(int)> f = [&](int x) { return fa[x] == x ? x : fa[x] = f(fa[x]); };
        for (int i = 0; i < k; i++)
            if (!dead[i]) { int x = f(e[i][1]), y = f(e[i][2]); if (x != y) fa[x] = y; }
        return f(a) == f(b);
    };

    long long cut = 0;
    for (int i = 0; i < k; i++) {
        dead[i] = 1;                                  // 先假装拆掉
        if (connected(e[i][1], e[i][2])) cut += e[i][0];
        else dead[i] = 0;                             // 拆了就断了 —— 放回去
    }

    cout << cut << '\n';
    return 0;
}

// ✗ P2820：把题目问的东西读反了 —— 输出「留下的最小」
//
// 题面问的是「被除去网线的 Σf(i,j) **最大值**」，而算出最小生成森林之后，
// 手边最现成的那个数是**留下的权和**。★ 顺手打出它，是这道题最常见的一发 WA。
// ⚠ 而它是个「每组都错」型的 bug ⇒ 官方样例当场挡住（打出 11，答案是 8）。

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

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

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

    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> e(k);
    long long total = 0;
    for (auto& t : e) { cin >> t[1] >> t[2] >> t[0]; total += t[0]; }

    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long keep = 0;
    for (auto& t : e) {
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        keep += t[0];
    }

    cout << keep << '\n';                             // ✗ 问的是删掉的，不是留下的
    return 0;
}

// ✗ P2820：以为图一定连通，非要收够 n − 1 条
//
// 题面从头到尾**没说过图是连通的** —— 它说的是「不改变原图节点的连通性」，
// 这句话恰恰是在提醒你：原来断开的两块，**删完之后也还得是断开的两块**。
//
// ★ 这一版一旦发现收不满 n − 1 条，就当成「有问题」按 0 处理；
//   ⚠ 而顺手写的生成器要是先造一棵树保证连通（[P3366 那条](/sol/p3366/)），
//   这个 bug 又是**精确的 0**。

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

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

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

    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> e(k);
    long long total = 0;
    for (auto& t : e) { cin >> t[1] >> t[2] >> t[0]; total += t[0]; }

    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long keep = 0;
    int cnt = 0;
    for (auto& t : e) {
        if (cnt == n - 1) break;
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        keep += t[0];
        cnt++;
    }

    if (cnt != n - 1) { cout << 0 << '\n'; return 0; } // ✗ 不连通就当没得删
    cout << total - keep << '\n';
    return 0;
}

// ✗ P2820：用邻接矩阵存这些网线
//
// `n ≤ 100` ⇒ 一张 101 × 101 的矩阵又小又顺手，很多人第一反应就是它。
// ★★ 而这道题**存不得**：它要的不只是「留下哪些」，还要**总权和** ——
//   而矩阵一个格子只放得下一条边，**同一对计算机之间的第二条网线会被直接覆盖掉**。
//
// ⚠ 题面里既没有「保证没有重边」，`k` 的上限也一个字没提
//   ⇒ 「同一对点之间有好几条线」是题面**允许**的输入。
// ★ 顺手写的生成器（在 n(n−1)/2 个点对里随机挑，不重复）**结构上**造不出重边
//   ⇒ 那一档是精确的 0。

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

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

int g[105][105];

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

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        int a, b, m;
        cin >> a >> b >> m;
        g[a][b] = g[b][a] = m;                        // ✗ 第二条线把第一条盖掉了
    }

    vector<array<int, 3>> e;
    long long total = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (g[i][j]) { e.push_back({g[i][j], i, j}); total += g[i][j]; }

    sort(e.begin(), e.end());
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long keep = 0;
    for (auto& t : e) {
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        keep += t[0];
    }
    cout << total - keep << '\n';
    return 0;
}