洛谷 P1195 口袋的天空

// P1195 口袋的天空 —— ★ 这一版就能 AC
//
// ★ 关键的一步只有一句话：**连成 K 个棉花糖 ⇒ 只要少合并 K − 1 次。**
//   从 n 朵孤零零的云开始，每合并一次连通块就少一个 ⇒ 要从 n 降到 K，
//   恰好合并 n − K 次。Kruskal 的循环**本来就在数这个**，把 `n − 1` 改成 `n − K` 就完了。
//
// 无解的判据也跟着白送：合并不满 n − K 次 ⇒ 原图的连通块本来就多于 K 个。
// ⚠ 外加一个题面允许、而 `n − K` 那个减法藏不住的边界：**K 可能比 n 还大**
//   （题面 1 ≤ K ≤ 10 而 1 ≤ N，n = 3 / K = 10 完全合法）—— n 朵云最多分成 n 组。

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

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

    if (k > n) { cout << "No Answer\n"; return 0; }    // ⚠ n 朵云分不出 k 个非空的堆

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

    int sum = 0, cnt = 0;
    for (auto& t : e) {
        if (cnt == n - k) break;                      // ★ 够了就停 —— 剩下的边一条都不要
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        sum += t[0];
        cnt++;
    }

    if (cnt == n - k) cout << sum << '\n';
    else cout << "No Answer\n";                       // 合并不满 ⇒ 连通块本来就多于 k 个
    return 0;
}

// ★ P1195 的另一条路：先求完整的最小生成树，再**删掉最大的 K − 1 条边**
//
// 这是很多人的第一反应，而它**是对的** —— 和正解 300 组逐组相等（见本页第 ② 步）。
// 一行就能证：Kruskal 是按权**升序**收边的，
// 完整 MST 的边集就是它收下的那 n − 1 条；「前 n − K 条」正是其中**最小的 n − K 条**
// ⇒ 「少收 K − 1 条」和「收完再删掉最大的 K − 1 条」是同一个集合。
//
// ⚠ 而它比正解**多了一处要小心的地方**：图不连通时压根没有「完整 MST」，
//   所以判无解的那一句还是得靠数合并次数 —— **绕的这一圈没省掉任何东西。**

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

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

    if (k > n) { cout << "No Answer\n"; return 0; }

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

    vector<int> used;                                 // 最小生成森林收下的边，权值升序
    for (auto& t : e) {
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        used.push_back(t[0]);
    }

    if ((int)used.size() < n - k) { cout << "No Answer\n"; return 0; }

    long long sum = 0;
    for (int i = 0; i < n - k; i++) sum += used[i];    // ★ 丢掉最后（最大）的 k − 1 条
    cout << sum << '\n';
    return 0;
}

// ✗ P1195：合并次数差一 —— 停在 `n − k + 1` 次
//
// 「连成 k 个棉花糖要合并几次」这句话在纸上很容易写反：
// 从 n 个块降到 k 个块要 **n − k** 次，而不是 n − k + 1（那会连成 k − 1 个）。
// ★ 它是个「每组都错」型的 bug —— 官方样例当场挡住（多收一条边，答案变大）。
// ⚠ 除非那一步没有边可收了（图刚好不够连），这时它反而和正解一样输出 No Answer。

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

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

    if (k > n) { cout << "No Answer\n"; return 0; }

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

    int sum = 0, cnt = 0, need = n - k + 1;           // ✗ 多合并了一次
    for (auto& t : e) {
        if (cnt == need) break;
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        sum += t[0];
        cnt++;
    }

    if (cnt == need) cout << sum << '\n';
    else cout << "No Answer\n";
    return 0;
}

// ✗ P1195：拿「答案还是 0」当「无解」的标志
//
// ★★ 这是「[答案有没有可能等于哨兵值](/sol/p1434/)」那条判据的又一个考场版 ——
//   而这道题的题面**明写着** `0 ≤ L < 10⁴`：**边权可以是 0，于是答案真的可以是 0。**
// ⚠ 而「答案恰好是 0」有**两条**路：① n == k（一条边都不用连）② 输入里有 0 权边。
//   顺手写的生成器一律从 1 开始撒边权 ⇒ 只剩下第一条路，抓获率被压掉一大半。
//
// ⚠⚠ 这一份第一版**同时**错了两件事（顺手把「合并够没够」那一句也删了），
//   于是量出来的抓获数其实是另一个 bug 的 —— 本章 wrongDij.cpp 顶上写着的那条规矩：
//   **错误版本也要干净，一份只错一件事**，否则说不清抓获率是谁的功劳。

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

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

    if (k > n) { cout << "No Answer\n"; return 0; }

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

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

    if (cnt != n - k) cout << "No Answer\n";           // ✓ 这一句是对的
    else if (sum == 0) cout << "No Answer\n";          // ✗ 「一分钱都没花」≠「连不出来」
    else cout << sum << '\n';
    return 0;
}

// ✗ P1195：忘了「怎么连都连不出 K 个棉花糖」那一支
//
// 和 [P3366](/sol/p3366/) 那个「忘了判 n − 1 条」是同一个形状：
// 它输出的不是垃圾，是**最小生成森林**的权和 —— 一个看着完全合理的数。
// ⚠ 而这道题比 P3366 更容易漏：那边题面把 `orz` 说了两遍，
//   这边 `No Answer` 只在输出格式里出现过一次。

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

int fa[1005];
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, k;
    cin >> n >> m >> k;
    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 sum = 0, cnt = 0;
    for (auto& t : e) {
        if (cnt == n - k) break;
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        sum += t[0];
        cnt++;
    }
    cout << sum << '\n';                              // ✗ 从头到尾没检查够不够
    return 0;
}

// ✗ P1195：忘了 K 可能比 N 还大
//
// 题面写的是 `1 ≤ N ≤ 10³` 和 `1 ≤ K ≤ 10` —— **两条范围各说各的，中间没有任何关系**。
// 于是 `n = 3, k = 10` 是一组完全合法的输入，而 n 朵云最多分成 n 组 ⇒ 答案是 No Answer。
//
// ★ 少了那一句之后 `n - k` 变成负数，循环第一次就 `cnt == n - k` 不成立、
//   一条边都不收，最后落到「合并不满」那一支 —— **它居然也输出 No Answer**。
// ⚠ 所以这个 bug 要现形，得**另有一条路**让 cnt 走到负数那个数……
//   实测它其实**只在 `n == k` 附近才和正解分家**，见本页第 ⑤ 步那张表。

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

int fa[1005];
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, k;
    cin >> n >> m >> k;
    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 sum = 0, cnt = 0;
    for (auto& t : e) {
        if (cnt >= n - k) break;                      // ✗ 少了 k > n 的那一句
        int x = find(t[1]), y = find(t[2]);
        if (x == y) continue;
        fa[x] = y;
        sum += t[0];
        cnt++;
    }

    if (cnt >= n - k) cout << sum << '\n';            // ✗ n − k 是负数时这里恒成立
    else cout << "No Answer\n";
    return 0;
}