POJ 3164 Command Network：朱劉算法求最小樹形圖

題目大意

給定 N（≤100）個節點座標與 M（≤10⁴）條可建立的有向邊，邊權為歐氏距離。節點 1 為根，求從根可達所有節點的最小樹形圖（有向最小生成樹）總權重。若不存在則輸出 poor snoopy。

解題思路：朱劉算法

1. 對每個非根節點，選入邊權最小的邊。
2. 若選出的邊形成環，縮環成一個超級節點，調整進入環的邊權（減去該節點原入邊權）。
3. 重複上述步驟直至無環，累加所有選入邊權即為答案。

核心代碼

#include <stdio.h>
#include <string.h>
#include <math.h>
#define INF (1<<30)

struct Point { double x, y; } p[10010];
struct Edge { int u, v; double w; } edge[10010*2];

double dist(int i, int j) {
    return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y));
}

int n, m, pre[10100], vis[10100], id[10010];
double in[10010];

double zhuliu(int root) {
    double ans = 0;
    while (true) {
        for (int i = 0; i < n; ++i) in[i] = INF;
        for (int i = 0; i < m; ++i) {
            int u = edge[i].u, v = edge[i].v;
            if (edge[i].w < in[v] && u != v) {
                pre[v] = u;
                in[v] = edge[i].w;
            }
        }
        for (int i = 0; i < n; ++i)
            if (i != root && in[i] == INF) return -1; // 有節點無入邊

        int cnt = 0;
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[root] = 0;
        for (int i = 0; i < n; ++i) {
            ans += in[i];
            int v = i;
            while (vis[v] != i && v != root && id[v] == -1) {
                vis[v] = i; v = pre[v];
            }
            if (v != root && id[v] == -1) {
                for (int u = pre[v]; u != v; u = pre[u]) id[u] = cnt;
                id[v] = cnt++;
            }
        }
        if (cnt == 0) break; // 無環

        for (int i = 0; i < n; ++i) if (id[i] == -1) id[i] = cnt++;
        for (int i = 0; i < m; ++i) {
            int u = edge[i].u, v = edge[i].v;
            edge[i].u = id[u]; edge[i].v = id[v];
            if (id[u] != id[v]) edge[i].w -= in[v];
        }
        n = cnt; root = id[root];
    }
    return ans;
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
        for (int i = 0; i < m; ++i) {
            scanf("%d%d", &edge[i].u, &edge[i].v);
            --edge[i].u; --edge[i].v;
            edge[i].w = (edge[i].u != edge[i].v) ? dist(edge[i].u, edge[i].v) : INF;
        }
        double ans = zhuliu(0);
        if (ans < 0) puts("poor snoopy");
        else printf("%.2lf\n", ans);
    }
    return 0;
}

關鍵點

• 邊權為歐氏距離，需用 double。
• 縮環時調整邊權：w -= in[v] 保證後續選擇正確。
• 若根無法到達某節點（in[i]==INF），直接返回 -1。

複雜度

• 時間：O(M log N) 或 O(NM)，此處實作為 O(NM)，N≤100, M≤10⁴ 足夠。
• 空間：O(N + M)