HDU 4786 Fibonacci Tree 題解：生成樹中白邊數構成斐波那契數的判定

題目大意

給定無向圖 N 點 M 邊，邊為白(1)或黑(0)。問是否存在生成樹使得白邊數為某個斐波那契數（1,2,3,5,8...）。N, M ≤ 1e5。

核心思路

生成樹白邊數範圍為 [min_white, max_white]。若區間內存在斐波那契數則答案為 Yes。因為可以在兩極端生成樹之間通過交換邊逐步調整白邊數，覆蓋所有中間值。

計算極值

• 最小白邊數：Kruskal 優先選黑邊（c=0 排前），統計生成樹中白邊數 bl。
• 最大白邊數：Kruskal 優先選白邊（c=1 排前），統計 bh。

先用並查集檢查圖連通性，不連通直接 No。

斐波那契預計算

預計算 fibo[i] ≤ 100000 的所有斐波那契數（約 25 個）。

AC 代碼 (C++)

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, fibo[50], f[100010];
struct Edge { int u, v, c; } e[100010];
bool cmp_min(Edge a, Edge b) { return a.c < b.c; } // 黑邊優先
bool cmp_max(Edge a, Edge b) { return a.c > b.c; } // 白邊優先
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
void unite(int x, int y) { x=find(x); y=find(y); if(x!=y) f[x]=y; }
int main() {
    fibo[1]=1; fibo[2]=2;
    for(int i=3;;i++) { fibo[i]=fibo[i-1]+fibo[i-2]; if(fibo[i]>=100000) break; }
    int T, cs=1; scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=0;i=2) { puts("No"); continue; }
        // 最小白邊
        sort(e,e+m,cmp_min);
        for(int i=1;i<=n;i++) f[i]=i;
        int bl=0, cnt=0;
        for(int i=0;i=bl && fibo[i]<=bh) { ok=true; break; }
        puts(ok?"Yes":"No");
    }
    return 0;
}