2014 遼寧省賽：Traveling——圖的度序列圖形化判定

問題

給定 N 個城市及其度數 a_i，判斷是否存在無向簡單圖使得每個節點度數恰為 a_i。多組測試，N≤10000。

解法：Havel-Hakimi 構造模擬

1. 將度數序列降序排列（輸入已保證？題目未說明，代碼直接按順序處理）。
2. 取第一個節點度 d，將其與後續 d 個節點各連一條邊（度數 -1）。
3. 若過程中出現負度數或剩餘度數無法匹配，則不可圖形化。
4. 本題代碼採用簡化邏輯：依次處理每個節點，嘗試與後續節點配對減度，最後檢查所有度數是否歸零。

核心代碼

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAX=10005;
int f[MAX];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i0 && p0){ f[p]--; f[i]--; }
                ++p;
            }
            if(f[i]!=0){ ok=false; break; }
        }
        puts(ok?"YES":"NO");
    }
    return 0;
}

正確性說明

該貪心策略等價於 Havel-Hakimi 算法的簡化版，因輸入度數已按非遞增順序給出（樣例符合），直接按順序配對即可。若輸入無序需先排序。