洛谷 P3366 【模板】最小生成树

// ✗ P3366 的第一版：忘了「选够 n − 1 条没有」
//
// 它在**连通**的图上一个字都不错 —— 官方样例照过，顺手写的对拍也照过。
// 图一旦不连通，它输出的是「最小生成**森林**」的权和：一个看着完全合理的正整数。
// ⇒ 这就是本页第 ③ 步那件事：**错法不输出垃圾，它输出一个像答案的东西。**

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

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

struct E { int u, v, w; };

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

    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto& t : e) cin >> t.u >> t.v >> t.w;

    sort(e.begin(), e.end(), [](const E& a, const E& b) { return a.w < b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;

    int sum = 0;
    for (const auto& t : e) {
        int x = find(t.u), y = find(t.v);
        if (x == y) continue;
        fa[x] = y;
        sum += t.w;
    }
    cout << sum << '\n';                   // ✗ 从头到尾没数过收了几条
    return 0;
}

// P3366【模板】最小生成树 —— ★ 这一版就能 AC
//
// Kruskal：把边按权排序，能连就连；数够 n − 1 条才算连通，否则输出 orz。
//
// ★ 这道题真正的考点不是「怎么求 MST」，是最后那一句：**图可能不连通**。
//   而顺手写的生成器（先造一棵树保证连通、再撒边）**一条不连通的图都造不出来**
//   ⇒ 那一档对拍是精确的 0，见 p3366Gen.cpp 的档位 1。
//
// 答案上界：(n − 1) × Z ≤ 4999 × 10⁴ = 49 990 000 < 2³¹ − 1（余量 43 倍）⇒ **不用 long long**。

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

int fa[5005];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }   // 路径压缩

struct E { int u, v, w; };

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

    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto& t : e) cin >> t.u >> t.v >> t.w;

    sort(e.begin(), e.end(), [](const E& a, const E& b) { return a.w < b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;

    int sum = 0, cnt = 0;
    for (const auto& t : e) {
        int x = find(t.u), y = find(t.v);
        if (x == y) continue;              // 同一棵树里再连就成环了
        fa[x] = y;
        sum += t.w;
        if (++cnt == n - 1) break;         // 够 n − 1 条，树已经长成
    }

    if (cnt == n - 1) cout << sum << '\n';
    else cout << "orz\n";                  // ⚠ 全小写。题面里那三个字母是 `orz`
    return 0;
}

// ✗ P3366：算法一个字没错，只是把 orz 写成了 Orz
//
// ★ 它是这一页唯一一个「和算法完全无关」的错法，也是唯一一个**对拍逐字节比才抓得到**的。
//   ⚠ 而它和上一版（忘了判连通）在**同一个档位**才现形 —— 图连通的时候两个都是精确的 0。

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

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

struct E { int u, v, w; };

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

    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto& t : e) cin >> t.u >> t.v >> t.w;

    sort(e.begin(), e.end(), [](const E& a, const E& b) { return a.w < b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;

    int sum = 0, cnt = 0;
    for (const auto& t : e) {
        int x = find(t.u), y = find(t.v);
        if (x == y) continue;
        fa[x] = y;
        sum += t.w;
        if (++cnt == n - 1) break;
    }

    if (cnt == n - 1) cout << sum << '\n';
    else cout << "Orz\n";                  // ✗ 题面写的是 orz，全小写
    return 0;
}

// ✗ P3366：并查集不 find，直接比 fa[x] 和 fa[y]
//
// 这是本章第 6 步点过的那个误解在真题上的价钱：**fa[x] 是「爸爸」，不是「祖宗」**。
// ⚠ 而它在官方样例上**打出的就是标准答案 7** —— 三条边一条不多一条不少。
//   理由能说清楚：那组数据里被合并的树一直只有两层，爸爸恰好就是祖宗。

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

int fa[5005];

struct E { int u, v, w; };

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

    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto& t : e) cin >> t.u >> t.v >> t.w;

    sort(e.begin(), e.end(), [](const E& a, const E& b) { return a.w < b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;

    int sum = 0, cnt = 0;
    for (const auto& t : e) {
        if (fa[t.u] == fa[t.v]) continue;  // ✗ 比的是爸爸，不是祖宗
        fa[t.u] = fa[t.v];                 // ✗ 改的也只是自己那一个格子
        sum += t.w;
        if (++cnt == n - 1) break;
    }

    if (cnt == n - 1) cout << sum << '\n';
    else cout << "orz\n";
    return 0;
}

// ✗ P3366：排序的比较函数写反了（从大到小）
//
// ★ 本章第 6 步那条恒等式：它不是「算错了」，它**精确地在解最大生成树**
//   —— 见 p3366Count.cpp 的 maxst 那一行，300 组逐个相等。
// ⇒ 说清楚一个 bug「算了什么」之后，它的所有表现都是白送的推论：
//   所有边权都相同的图上它是对的，别的图上它每一组都错（⇒ 官方样例当场挡住）。

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

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

struct E { int u, v, w; };

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

    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto& t : e) cin >> t.u >> t.v >> t.w;

    sort(e.begin(), e.end(), [](const E& a, const E& b) { return a.w > b.w; });  // ✗ 反了
    for (int i = 1; i <= n; i++) fa[i] = i;

    int sum = 0, cnt = 0;
    for (const auto& t : e) {
        int x = find(t.u), y = find(t.v);
        if (x == y) continue;
        fa[x] = y;
        sum += t.w;
        if (++cnt == n - 1) break;
    }

    if (cnt == n - 1) cout << sum << '\n';
    else cout << "orz\n";
    return 0;
}

// ⚠ P3366：并查集写对了，只是**没有路径压缩**（find 老老实实往上爬）
//
// ★★ 这一版的答案**永远是对的** —— 对拍一万轮也抓不到它。
//    它坏的不是答案，是复杂度：单次 find 最坏 O(n)，而这道题有 2 × 10⁵ 条边。
// ⇒ 「答案对但跑不完」只能靠**数次数 ＋ 造对形状**发现（[P5019] 那条）。
//    造法见 p3366Gen.cpp 档位 4：先用最轻的那批星形边把并查集**拉成一条链**
//    （`fa[find(x)] = find(y)` 每次都把整棵树挂到一个新点下面），
//    再让剩下的十几万条「两头已经在同一棵树里」的边，每一条都从链底爬到链顶。
//    ⚠ 关键是**最后一条边留到最重** —— 否则树提前长成，那句 break 会救了它。

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

int fa[5005];

int find(int x) {                          // ⚠ 少的就是 `fa[x] =` 那半句
    while (fa[x] != x) x = fa[x];
    return x;
}

struct E { int u, v, w; };

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

    int n, m;
    cin >> n >> m;
    vector<E> e(m);
    for (auto& t : e) cin >> t.u >> t.v >> t.w;

    sort(e.begin(), e.end(), [](const E& a, const E& b) { return a.w < b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;

    int sum = 0, cnt = 0;
    for (const auto& t : e) {
        int x = find(t.u), y = find(t.v);
        if (x == y) continue;
        fa[x] = y;
        sum += t.w;
        if (++cnt == n - 1) break;
    }

    if (cnt == n - 1) cout << sum << '\n';
    else cout << "orz\n";
    return 0;
}

// ★ P3366 的另一条路：堆优化 Prim —— 它也能 AC
//
// 本章第 7 步那句话：它和第 32 章的堆优化 Dijkstra **只差一个字**
//   （Dijkstra 比的是 `dist[u] + w`，Prim 比的就是 `w`）。
// ⚠ 而这道题上它**比 Kruskal 慢**：n = 5000 / m = 2 × 10⁵ 是一张**稀疏图**，
//   Kruskal 那一遍 sort 又快又便宜。实测见本页第 ⑥ 步那张表。

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;                // ⚠ (边权, 点号) —— 和第 32 章堆里那个顺序一样

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

    int n, m;
    cin >> n >> m;
    vector<vector<pii>> g(n + 1);          // g[u] 里存 (邻居, 边权)
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});            // 无向图，存两遍
    }

    vector<char> in(n + 1, 0);
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, 1});                        // 从 1 号点开始长

    int sum = 0, cnt = 0;
    while (!q.empty()) {
        auto [w, u] = q.top();
        q.pop();
        if (in[u]) continue;               // 已经在树里了，这条是过期货
        in[u] = 1;
        sum += w;
        cnt++;
        for (auto [v, c] : g[u]) if (!in[v]) q.push({c, v});
    }

    if (cnt == n) cout << sum << '\n';     // ⚠ Prim 数的是**点**，够 n 个才连通
    else cout << "orz\n";
    return 0;
}