最小生成树：Prim 与 Kruskal

1. 把所有 m 条边存进数组，按权值 升序 排序        // 目光盯在"边"上
2. 初始化并查集：每个点各自一个集合
3. 依次扫描每条边 (u, v, w)：
       if (find(u) != find(v)) {               // 两点尚未连通 → 不会成环
           合并 find(u) 与 find(v);
           总代价 += w;  选中边数++;
           if (选中边数 == n - 1) break;    // 已经连成一棵树了
       }
4. 若选中边数 < n - 1，说明原图不连通，无解

// n 个点，邻接矩阵 g[i][j]（不连通为 INF）
const int INF = 0x3f3f3f3f;
int n, g[1005][1005], lowcost[1005];
bool vis[1005];

long long prim() {
    for (int i = 1; i <= n; i++) lowcost[i] = INF;
    lowcost[1] = 0;                       // 从 1 号点开始，自己到点集距离为 0

    long long total = 0;
    for (int round = 1; round <= n; round++) {
        int u = -1;
        for (int i = 1; i <= n; i++)           // 找未加入点中 lowcost 最小的
            if (!vis[i] && (u == -1 || lowcost[i] < lowcost[u])) u = i;

        if (u == -1 || lowcost[u] == INF) break;  // 图不连通
        vis[u] = true;
        total += lowcost[u];                  // 注意：不加 g[?][u]，加的就是 lowcost 本身

        for (int v = 1; v <= n; v++)         // 用 u 松弛其他未加入的点
            if (!vis[v] && g[u][v] < lowcost[v]) lowcost[v] = g[u][v];
    }

    for (int i = 1; i <= n; i++) if (!vis[i]) return -1;  // 有漏点 → 不连通
    return total;
}

struct Edge { int to, w, nxt; } e[MAXM * 2];
int head[MAXN], cntE = 0;
void add(int u, int v, int w) {
    e[++cntE] = {v, w, head[u]}; head[u] = cntE;
}

typedef pair<int,int> PII;    // (到点集的距离, 点编号)
priority_queue<PII, vector<PII>, greater<PII>> pq;

long long prim() {
    vector<bool> vis(n + 1, false);
    pq.push({0, 1});               // 从 1 号点出发
    long long total = 0;
    int picked = 0;

    while (!pq.empty() && picked < n) {
        PII cur = pq.top(); pq.pop();
        int d = cur.first, u = cur.second;
        if (vis[u]) continue;          // 过期候选，跳过
        vis[u] = true;
        total += d; picked++;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (!vis[v]) pq.push({e[i].w, v});   // 直接压入单边权，不累加
        }
    }
    return picked == n ? total : -1;
}

/* 思路：先 Kruskal 求 MST，再枚举非树边做"加边删边" */
long long W;                       // MST 总权值
vector<int> tree[MAXN];            // 只含树边的邻接表
int maxEdgeOnPath, tx, ty;         // u→v 路径上的最大边权及其端点

void dfsPath(int u, int fa, int target) {
    if (u == target) { maxEdgeOnPath = 0; return; }
    // 在树上找 u→target 的路径，记录路径上的最大边（此处用简单 DFS）
    for (int v : tree[u]) if (v != fa) dfsPath(v, u, target);
}

long long secondMST() {
    long long ans = LLONG_MAX;
    for (auto& ed : edges) {
        if (ed.inTree) continue;                  // 只看非树边
        int mw = 0;                            // 路径 (u,v) 上的最大树边权
        for (int k = 0; k < 17; k++)              // 倍增查询路径最大值
            mw = max(mw, queryMax(ed.u, ed.v, k));
        if (ed.w > mw) ans = min(ans, W + ed.w - mw);   // 严格次小
    }
    return ans;
}

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

const int MAXN = 5005, MAXM = 200005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }   // 按权值升序
} e[MAXM];

int fa[MAXN], rk[MAXN];              // 并查集：父节点 + 秩

int find(int x) {
    while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }   // 路径压缩（迭代版）
    return x;
}

bool merge(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return false;                 // 已连通，会成环
    if (rk[a] < rk[b]) swap(a, b);              // 按秩合并
    fa[b] = a;
    if (rk[a] == rk[b]) rk[a]++;
    return true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    for (int i = 1; i <= n; i++) fa[i] = i;

    sort(e + 1, e + m + 1);                  // 第 1 步：边排序

    long long total = 0;
    int picked = 0;
    for (int i = 1; i <= m && picked < n - 1; i++) {
        if (merge(e[i].u, e[i].v)) {             // 第 2 步：不成环就选
            total += e[i].w;
            picked++;
        }
    }

    if (picked < n - 1) cout << "orz" << "\n";  // 图不连通
    else cout << total << "\n";
    return 0;
}

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

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, g[MAXN][MAXN];
int lowcost[MAXN];        // 未加入点 i 到点集 S 的最短单边权
bool vis[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
            if (g[i][j] == -1) g[i][j] = INF;     // -1 表示不连通
        }

    for (int i = 1; i <= n; i++) lowcost[i] = INF;
    lowcost[1] = 0;                            // 从 1 号点开始

    long long total = 0;
    for (int round = 1; round <= n; round++) {
        int u = 0;                             // 找 lowcost 最小的未访问点
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (u == 0 || lowcost[i] < lowcost[u])) u = i;

        if (u == 0 || lowcost[u] == INF) break;     // 图不连通

        vis[u] = true;
        total += lowcost[u];
        for (int v = 1; v <= n; v++)
            if (!vis[v] && g[u][v] < lowcost[v]) lowcost[v] = g[u][v];
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) if (vis[i]) cnt++;
    if (cnt < n) cout << -1 << "\n";
    else cout << total << "\n";
    return 0;
}

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

const int MAXN = 1005, MAXM = 10005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }
} e[MAXM];

int fa[MAXN];
int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    if (k > n) { cout << "No Answer" << "\n"; return 0; }   // 块数不能超过点数

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

    long long total = 0;
    int blocks = n;                        // 当前连通块个数，初始为 n
    for (int i = 1; i <= m && blocks > k; i++) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a != b) {
            fa[a] = b;
            total += e[i].w;
            blocks--;                        // 合并两块，块数减一
        }
    }

    if (blocks > k) cout << "No Answer" << "\n";   // 边不够，达不到 k 块
    else cout << total << "\n";
    return 0;
}

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

const int MAXN = 5005, MAXM = 200005;
struct Edge { int u, v, w; } e[MAXM];
bool cmp(const Edge& a, const Edge& b) { return a.w < b.w; }

int fa[MAXN], rk[MAXN];
int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(e + 1, e + m + 1, cmp);

    long long total = 0;
    int picked = 0;
    for (int i = 1; i <= m && picked < n - 1; i++) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a == b) continue;
        if (rk[a] < rk[b]) swap(a, b);
        fa[b] = a; if (rk[a] == rk[b]) rk[a]++;
        total += e[i].w;
        picked++;
    }
    if (picked < n - 1) cout << "orz" << "\n";
    else cout << total << "\n";
    return 0;
}

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

const int INF = 0x3f3f3f3f, MAXN = 1005;
int n, m, g[MAXN][MAXN], lowcost[MAXN];
bool vis[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) g[i][j] = INF;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u][v] = min(g[u][v], w);           // 处理重边，取较小者
        g[v][u] = min(g[v][u], w);
    }

    for (int i = 1; i <= n; i++) lowcost[i] = INF;
    lowcost[1] = 0;

    long long total = 0;
    for (int r = 1; r <= n; r++) {
        int u = 0;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (u == 0 || lowcost[i] < lowcost[u])) u = i;
        if (lowcost[u] == INF) { cout << -1; return 0; }
        vis[u] = true; total += lowcost[u];
        for (int v = 1; v <= n; v++)
            if (!vis[v] && g[u][v] < lowcost[v]) lowcost[v] = g[u][v];
    }
    cout << total << "\n";
    return 0;
}

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

const int MAXN = 1005, MAXM = 10005;
struct Edge { int u, v, w; } e[MAXM];
bool cmp(const Edge& a, const Edge& b) { return a.w < b.w; }
int fa[MAXN];
int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    if (k > n) { cout << "No Answer"; return 0; }
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(e + 1, e + m + 1, cmp);

    long long total = 0;
    int blocks = n;
    for (int i = 1; i <= m && blocks > k; i++) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a == b) continue;
        fa[a] = b; total += e[i].w; blocks--;
    }
    if (blocks > k) cout << "No Answer" << "\n";
    else cout << total << "\n";
    return 0;
}

/* ================= Kruskal（稀疏图） ================= */
struct Edge { int u, v, w; };
Edge e[MAXM];
int fa[MAXN];

int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; }

long long kruskal(int n, int m) {
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(e + 1, e + m + 1, [](const Edge& a, const Edge& b) { return a.w < b.w; });

    long long total = 0;
    int picked = 0;
    for (int i = 1; i <= m; i++) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a == b) continue;               // 成环，跳过
        fa[a] = b;
        total += e[i].w;
        if (++picked == n - 1) break;      // 连成一棵树，提前结束
    }
    return picked == n - 1 ? total : -1;  // -1 表示不连通
}

/* ================= Prim（稠密图，O(n^2)） ================= */
int g[MAXN][MAXN], lowcost[MAXN];
bool vis[MAXN];

long long prim(int n) {
    for (int i = 1; i <= n; i++) { lowcost[i] = INF; vis[i] = false; }
    lowcost[1] = 0;

    long long total = 0;
    for (int r = 1; r <= n; r++) {
        int u = 0;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (u == 0 || lowcost[i] < lowcost[u])) u = i;
        if (u == 0) return -1;                 // 不连通
        vis[u] = true;
        total += lowcost[u];
        for (int v = 1; v <= n; v++)
            if (!vis[v] && g[u][v] < lowcost[v]) lowcost[v] = g[u][v];
    }
    return total;
}