洛谷 P1547 [USACO05MAR] Out of Hay S

// P1547 [USACO05MAR] Out of Hay S —— ★ 这一版就能 AC
//
// ★ 关键的一步只有半行：Kruskal 是**按权升序**收边的
//   ⇒ 「最小生成树里最长的那条」就是**它收下的最后一条**。
//   连 max 都不用取（取了也没错，见 p1547All.cpp 那个位置写错的反面教材）。
//
// ⚠ 题面明写着两句保证，各值一件事：
//   ①「所有的农场之间都是连通的」⇒ **不用判无解**（对照 [P3366](/sol/p3366/) 的 orz）；
//   ②「所有道路的总长度不超过 10⁹」—— ★ 这句的主语是**总和**，
//      于是连「权和」都撑不破 int，更别说单条边 ⇒ **不用 long long**。
// ⚠ 另外题面明说「有些农场之间存在着多条道路」—— 重边。Kruskal 天然不怕，
//   而换成邻接矩阵存图就得当心（见 p1547Mat.cpp）。

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

int fa[2005];
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, m;
    cin >> n >> m;
    vector<array<int, 3>> e(m);
    for (auto& t : e) cin >> t[1] >> t[2] >> t[0];    // 读进来是 A B L，存成 (L, A, B)

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

    int ans = 0, cnt = 0;
    for (auto& t : e) {
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;                         // ⚠ 跳过的边**不算数**，位置很要紧
        fa[x] = y;
        ans = t[0];                                   // ★ 升序收边 ⇒ 最后收下的就是最长的
        if (++cnt == n - 1) break;
    }
    cout << ans << '\n';
    return 0;
}

// ✗ P1547：打出了最小生成树的**权和**
//
// 这道题挂在第 34 章的题单里，前面几道又全是「求权和」——
// 于是写完 Kruskal 顺手 `cout << sum` 是最自然不过的一发 WA。
// ★ 它是「每组都错」型（除非那棵树只有一条边），官方样例当场挡住（66 vs 43）。

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

int fa[2005];
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, m;
    cin >> n >> m;
    vector<array<int, 3>> e(m);
    for (auto& t : e) cin >> t[1] >> t[2] >> t[0];

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

    long long sum = 0;
    int cnt = 0;
    for (auto& t : e) {
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        sum += t[0];                                  // ✗ 题目问的是最长的那一条，不是和
        if (++cnt == n - 1) break;
    }
    cout << sum << '\n';
    return 0;
}

// ⚠⚠ P1547：取 max 那一行写在了 `continue` 前面 —— 而它**一次都没错**
//
// 草稿里把这一版当成错法收了进来，理由听着很顺：「被判环跳过的边也被算进 max 了，
// 那不就成了**全图**最长的边？」——**四个档 1200 轮，被抓 0 次。**
//
// ★★★ 一行就能证明它为什么对：
//   边是**升序**扫的，而 Kruskal 收够 `n − 1` 条就 `break`
//   ⇒ **被扫到的每一条边，都不比最后收下的那一条长。**
//   于是 `max` 取到的就是最后收下的那条 —— 和正解一模一样。
//
// ⚠ 而这个「精确的 0」**配了自检才敢写**：把那句 `break` 去掉，它当场就错
//   （见 p1547NoBreak.cpp，档 0 抓 **203 / 300**）。
//   ⇒ 「[一个反例都没有](/sol/p1439/)」和「这段代码根本没在跑」输出一模一样。
//
// ⇒ ★★ 真正的结论不是「max 写哪儿都行」，是**「那句 break 在替它兜底」** ——
//   两处细节各自都不起眼，凑在一起才让它是对的。

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

int fa[2005];
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, m;
    cin >> n >> m;
    vector<array<int, 3>> e(m);
    for (auto& t : e) cin >> t[1] >> t[2] >> t[0];

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

    int ans = 0, cnt = 0;
    for (auto& t : e) {
        ans = max(ans, t[0]);                         // ✗ 跳过的边也被算进来了
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        if (++cnt == n - 1) break;
    }
    cout << ans << '\n';
    return 0;
}

// ✗ P1547：邻接矩阵 ＋ 朴素 Prim，重边直接赋值不取 min
//
// `n ≤ 2000` ⇒ 矩阵 2001 × 2001 × 4 ≈ **16 MB**（题面给 125 MB），**放得下**，
// 而 `O(n²) = 4 × 10⁶` 也够快 ⇒ 朴素 Prim 在这道题上是一条**真能走通**的路。
//
// ★★ 可它比 Kruskal 多背了一个包袱：**题面明写着「有些农场之间存在着多条道路」。**
//   矩阵一个格子只放得下一条边，顺手写 `g[a][b] = l` 的话，
//   **后读进来的那条会把先读进来的短边盖掉**。
// ⇒ 这是 [B3647 那个坑](/sol/b3647/) 在 MST 上的复现，而这次**题面自己提醒过你了**。

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

const int INF = 0x3f3f3f3f;
static int g[2005][2005];

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

    int n, m;
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < m; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        g[a][b] = g[b][a] = l;                        // ✗ 没有 min —— 重边把短的盖掉了
    }

    vector<char> in(n + 1, 0);
    vector<int> best(n + 1, INF);
    best[1] = 0;
    int ans = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!in[i] && (u < 0 || best[i] < best[u])) u = i;
        in[u] = 1;
        ans = max(ans, best[u]);
        for (int i = 1; i <= n; i++)
            if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }
    cout << ans << '\n';
    return 0;
}

// ★ P1547 的另一条路：朴素 Prim（矩阵存图，**重边取 min**）—— 它也能 AC
//
// 和上面那份 p1547Mat.cpp 只差 `min(...)` 那半行 ——
// ★ 这一对是本页最干净的对照：**同一个写法，加不加那半行就是正解和错法。**
// 矩阵 2001 × 2001 × 4 ≈ 16 MB，`O(n²) = 4 × 10⁶`，顶格本机见本页第 ⑥ 步那张表。

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

const int INF = 0x3f3f3f3f;
static int g[2005][2005];

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

    int n, m;
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < m; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        g[a][b] = g[b][a] = min(g[a][b], l);          // ★ 就是这半行
    }

    vector<char> in(n + 1, 0);
    vector<int> best(n + 1, INF);
    best[1] = 0;
    int ans = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!in[i] && (u < 0 || best[i] < best[u])) u = i;
        in[u] = 1;
        ans = max(ans, best[u]);
        for (int i = 1; i <= n; i++)
            if (!in[i] && g[u][i] < best[i]) best[i] = g[u][i];
    }
    cout << ans << '\n';
    return 0;
}

// ✗ P1547：按 USACO 原版的格式，输出了**两个**数
//
// ★ 这个坑不在算法里，在「你照着哪一份题面写」上：
//   USACO 原题要的是「最长边 ＋ 有多少条边的长度等于它」，
//   而本地存的这份洛谷题面（见页头「题目原文」）写得很清楚：
//   输出格式是「**一个整数**」，样例输出也只有一个 `43`。
// ⇒ 网上不少题解是照原版写的，**照抄会多打一个数**。
// ⚠ 两边不一致时信原站 —— 这也正是每个解析页都要把题面存一份的理由。

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

int fa[2005];
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, m;
    cin >> n >> m;
    vector<array<int, 3>> e(m);
    for (auto& t : e) cin >> t[1] >> t[2] >> t[0];

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

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

    int same = 0;
    for (auto& t : e) if (t[0] == ans) same++;
    cout << ans << ' ' << same << '\n';               // ✗ 这一行多出来的那个数
    return 0;
}