HDU 4786 Fibonacci Tree：最小/最大生成樹白邊數區間判定斐波那契數

HDU 4786：生成樹白邊數是否為斐波那契數

圖邊染黑(0)/白(1)，生成樹白邊數即權值和。求是否存在生成樹使白邊數為斐波那契數（1,2,3,5,8...）。
核心猜想：所有生成樹的白邊數構成連續整數區間 [minWhite, maxWhite]。若區間內含斐波那契數則答案 Yes。
證據：任意非最大生成樹可通過換邊（白換黑）增加白邊數 1，形成連續過渡。

算法流程

1. Kruskal 求最小生成樹（黑邊優先，權 0）：白邊數 = minWhite。
2. Kruskal 求最大生成樹（白邊優先，權 1）：白邊數 = maxWhite。
3. 預計算斐波那契數至 1e5。
4. 判斷 [minWhite, maxWhite] 內是否有斐波那契數。

完整代碼

#include <bits/stdc++.h>
using namespace std;
struct Edge{int u,v,w; bool operator<(Edge o)const{return w fib={1,2}; while(fib.back()<100000) fib.push_back(fib.end()[-1]+fib.end()[-2]);
    int T; scanf("%d",&T);
    for(int cs=1;cs<=T;cs++){
        int n,m; scanf("%d%d",&n,&m);
        vector e(m);
        for(int i=0;ib.w:a.w=mn && f<=mx){ok=true;break;}
        printf("Case #%d: %s\n",cs,ok?"Yes":"No");
    }
    return 0;
}

正確性說明

雖無嚴格證明，但交換論證：若存在白邊數為 k 和 k+2 的生成樹，通常可構造 k+1。測試數據通過。類似「生成樹權值譜連續」猜想在許多問題中成立。