洛谷 P1546 [USACO3.1] 最短网络 Agri-Net

// P1546 [USACO3.1] 最短网络 —— ★ 这一版就能 AC
//
// 题目直接给一张 n × n 的距离矩阵 ⇒ 这是一张**完全图**（稠密到极点）。
// [本章第 7 步](/ch/34-mst/)那份朴素 Prim 正好对上：O(n²)，一个堆都不用。
//
// ★★ 而这道题真正会挂人的地方**不在算法里**，在输入格式那句话上：
//   「由于每行 80 个字符的限制，因此，某些行会紧接着另一些行。」
//   —— 用 `cin >>` 读的话，这句话对你**完全没有影响**（它把所有空白符一视同仁）；
//      而按行读（getline 再切）当场就死。见 p1546Line.cpp。

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

int g[105][105];

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> g[i][j];   // ★ 换不换行，它一个字都不在乎

    vector<char> in(n + 1, 0);
    vector<int> best(n + 1, INT_MAX);
    best[1] = 0;

    int sum = 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;
        sum += best[u];
        for (int i = 1; i <= n; i++)                  // ★ 比的是 g[u][i]，不是 best[u] + g[u][i]
            if (!in[i]) best[i] = min(best[i], g[u][i]);
    }
    cout << sum << '\n';
    return 0;
}

// ✗ P1546：按行读矩阵 —— 题面那句「某些行会紧接着另一些行」就是冲它来的
//
// ★★ 它在**规整**的矩阵上一个字不错（官方样例照过、顺手写的对拍 300 轮全绿），
//    只要输入真的按题面说的那样折了行，它当场读崩。
// ⇒ 这是这一页唯一一个「**对拍在默认档上永远抓不到**」的错法 ——
//    因为生成器自己造的矩阵是规整的，得专门造一档折行的（p1546Gen.cpp 档位 1）。

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

int g[105][105];

int main() {
    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int i = 1; i <= n; i++) {
        string line;
        getline(cin, line);                           // ✗ 假定「一行正好 n 个数」
        istringstream ss(line);
        for (int j = 1; j <= n; j++) ss >> g[i][j];   // 读不满就留着上一轮的垃圾
    }

    vector<char> in(n + 1, 0);
    vector<int> best(n + 1, INT_MAX);
    best[1] = 0;
    int sum = 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;
        sum += best[u];
        for (int i = 1; i <= n; i++)
            if (!in[i]) best[i] = min(best[i], g[u][i]);
    }
    cout << sum << '\n';
    return 0;
}

// ✗ P1546：把矩阵里的 0 当成「这两点之间没有路」
//
// 这是一个**从题面推不出来、只能从题面「没说什么」看出来**的坑：
// 题面只写了「每两个农场间的距离不会超过 10⁵」，**一个字都没说距离 ≥ 1**。
//
// ★ 而顺手写的生成器一律从 1 开始撒距离 ⇒ 这一档是**精确的 0**（见 p1546Gen.cpp 档位 2）。
//   和[第 33 章 P1266](/sol/p1266/) 那个「`V = 0` 的边」是同一个形状。

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

const int INF = 0x3f3f3f3f;
int g[105][105];

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            g[i][j] = x ? x : INF;                    // ✗ 「0 就是没边」——对角线是这样，别处不是
        }

    vector<char> in(n + 1, 0);
    vector<int> best(n + 1, INF);
    best[1] = 0;
    int sum = 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;
        sum += best[u];
        for (int i = 1; i <= n; i++)
            if (!in[i]) best[i] = min(best[i], g[u][i]);
    }
    cout << sum << '\n';
    return 0;
}

// ✗ P1546：Prim 手滑写成了 Dijkstra
//
// [本章第 7 步](/ch/34-mst/)说过这两份代码「只差一个字」——
// 差的就是松弛那一行：Prim 比的是 `g[u][i]`（到**树**的距离），
// Dijkstra 比的是 `best[u] + g[u][i]`（到**起点**的距离）。
//
// ⚠ 照本章 wrongDij.cpp 的规矩，这一份累加的是「真正用到的那条边的权」，
//   而不是 best[u] —— 否则它连「一棵树的权值和」都不是了，错得太明显反而没有教学价值。
//   ★ 它的意思是：**它给出的是一棵真的树（最短路径树），只是选错了那棵。**

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

int g[105][105];

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> g[i][j];

    vector<char> in(n + 1, 0);
    vector<int> best(n + 1, INT_MAX), from(n + 1, 0);  // from[v] = 把 v 够进来的那条边的权
    best[1] = 0;

    int sum = 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;
        sum += from[u];
        for (int i = 1; i <= n; i++)
            if (!in[i] && best[u] + g[u][i] < best[i]) {   // ✗ 多了「best[u] +」这一截
                best[i] = best[u] + g[u][i];
                from[i] = g[u][i];
            }
    }
    cout << sum << '\n';
    return 0;
}

// ✗ P1546：挑点的时候忘了跳过「已经在树里」的
//
// 少的就是那半句 `!in[i]`。它每一轮都会挑中 `best` 最小的那个点 ——
// 而已经入树的点 best 已经被定死、往往就是全场最小的 ⇒ **它会反复挑同一个点**，
// 于是树根本长不起来，`sum` 少加一大截。
// ★ 这是一个「每组都错」型的 bug ⇒ 官方样例当场挡住。

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

int g[105][105];

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> g[i][j];

    vector<char> in(n + 1, 0);
    vector<int> best(n + 1, INT_MAX);
    best[1] = 0;
    int sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (u < 0 || best[i] < best[u]) u = i;    // ✗ 没有 !in[i]
        in[u] = 1;
        sum += best[u];
        for (int i = 1; i <= n; i++)
            if (!in[i]) best[i] = min(best[i], g[u][i]);
    }
    cout << sum << '\n';
    return 0;
}

// ★ P1546 的另一条路：Kruskal —— 它也能 AC
//
// 矩阵给的是完全图 ⇒ 要先把 n(n−1)/2 = 4950 条边**摊开**，再排序。
// ⚠ 这一步在 n = 100 时无所谓（4950 条），但它是这道题和 [P3366](/sol/p3366/) 的分水岭：
//   那边 n = 5000、m = 2 × 10⁵（稀疏），这边 n = 100、m = 4950（稠密到满）。
//   ⇒ **「用 Kruskal 还是 Prim」的主语是「点多还是边多」**，见本页第 ⑤ 步那张表。

#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;
    cin >> n;
    vector<array<int, 3>> e;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int w;
            cin >> w;
            if (i < j) e.push_back({w, i, j});        // 只取上三角，矩阵是对称的
        }

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

    int sum = 0, 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;
}