1210 - 圖論 之 簡單圖測試

Link: http://tioj.ck.tp.edu.tw/problems/1210
一開始想說隨便亂連，如果發現不能連就不是簡單圖，後來發現是假解，試試以下這筆測資:

3
1 1 2
0

如果一開始前2個點連在一起，就會造成第3個點無法連邊，但事實上可以前2點分別和第3點相連

後來改變作法，每次從度數最大的點開始連就對了，查了一下原來這是Havel定理
這篇好像說明得不錯，有Havel定理的證明
http://blog.csdn.net/shuangde800/article/details/7857246

發現UVA上有一模一樣的題目(僅輸出格式不同): UVa 10720
POJ上的類似題，需要輸出相連關係: POJ 1659

AC code

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[10000];
bool solve()
{
    for(int i=0;i<n;i++)
    {
        sort(a+i,a+n,greater<int>());
        for(int j=i+1;j<n&&a[i]>0;j++)
        {
            a[i]--;
            a[j]--;
            if(a[j]<0) return 0;
        }
        if(a[i]>0) return 0;
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    while(cin>>n,n)
    {
        for(int i=0;i<n;i++)
            cin>>a[i];
        if(solve())
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
}