HDOJ 4786 Fibonacci Tree：克魯斯卡爾算法與費波納契數應用

問題描述

給定一個包含 N 個頂點和 M 條邊的無向圖，每條邊被染成白色或黑色。問是否存在一棵生成樹，使得其中白色邊的數量是某個正費波納契數（費波納契數列定義為 1, 2, 3, 5, 8, ...）。

輸入包含多組測試數據。每組給出 N (≤ 10^5) 和 M (≤ 10^5)，隨後 M 行描述邊：u, v, c（c=1 為白邊，c=0 為黑邊）。對每組輸出 "Case #x: Yes" 或 "No"。

解題思路

本題結合了最小生成樹與費波納契數性質。關鍵觀察：生成樹中白邊數量的範圍是連續的。我們可以分別求出生成樹中白邊數量的最小值和最大值，然後判斷該區間內是否包含費波納契數。

• 最小白邊數：將黑邊權重設為 0，白邊權重設為 1，跑 Kruskal 求最小生成樹，得到的白邊數即為最小值 minWhite。
• 最大白邊數：將白邊權重設為 0，黑邊權重設為 1，跑 Kruskal 求最小生成樹，白邊數即為最大值 maxWhite。

若區間 [minWhite, maxWhite] 內存在費波納契數，則答案為 Yes，否則為 No。

算法流程

1. 預計算足夠大的費波納契數（直到超過 N）。
2. 對每組測試數據，分別按上述兩種權重設置跑兩次 Kruskal，得到 minWhite 和 maxWhite。
3. 遍歷費波納契數列，若有數落在 [minWhite, maxWhite] 內，輸出 Yes，否則 No。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 100100;
struct Edge { int u, v, w; } edges[MAXN];
int parent[MAXN];
int fib[MAXN];
int n, m;

int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

int kruskal(bool minimizeWhite) {
    for (int i = 1; i <= n; ++i) parent[i] = i;
    // 設置權重：若 minimizeWhite，白邊 w=1，黑邊 w=0；反之亦然
    for (int i = 0; i < m; ++i) {
        if (minimizeWhite) edges[i].w = edges[i].c; // c=1 白
        else edges[i].w = 1 - edges[i].c;
    }
    sort(edges, edges + m, [](const Edge& a, const Edge& b){ return a.w < b.w; });
    int whiteCnt = 0, edgeCnt = 0;
    for (int i = 0; i < m && edgeCnt < n-1; ++i) {
        int u = find(edges[i].u), v = find(edges[i].v);
        if (u != v) {
            parent[u] = v;
            if (edges[i].c == 1) ++whiteCnt;
            ++edgeCnt;
        }
    }
    return whiteCnt;
}

int main() {
    fib[0] = 1; fib[1] = 2;
    for (int i = 2; i < MAXN; ++i) fib[i] = fib[i-1] + fib[i-2];
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].c);
        }
        int minW = kruskal(true);
        int maxW = kruskal(false);
        bool ok = false;
        for (int i = 0; fib[i] <= maxW; ++i) {
            if (fib[i] >= minW) { ok = true; break; }
        }
        printf("Case #%d: %s\n", cas, ok ? "Yes" : "No");
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(M log M) 每次 Kruskal，兩次共 O(M log M)，M ≤ 10^5，可接受。
• 空間複雜度：O(N + M)。

總結

本題巧妙地將「存在費波納契數白邊的生成樹」轉化為「白邊數量區間包含費波納契數」，利用 Kruskal 算法求極值，體現了圖論與數論結合的思想。