POJ1659 Frogs' Neighborhood（Havel定理）

给一个无向图的度序列判定是否可图化，并求方案：

• 可图化的判定：d1+d2+……dn=0（mod 2）。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。
• 可简单图化的判定（Havel定理）：把序列排成不增序，即d1>=d2>=……>=dn，则d可简单图化当且仅当d’={d2-1，d3-1，……d(d1+1)-1， d(d1+2)，d(d1+3)，……dn}可简单图化。简单的说，把d排序后，找出度最大的点（设度为d1），把它与度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。

这一题把青蛙看成点，邻居关系看成边，可以知道这是简单图（无重边、自环）。因此用Havel定理来判定，并且用上述方法来构造出一个解：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct Frog{
    int pos,deg;
    bool operator<(const Frog &f)const{
        return deg>f.deg;
    }
}frog[11];

int n;
bool ans[11][11];
bool Havel(){
    for(int i=0; i<n; ++i){
        sort(frog+i,frog+n);
        for(int j=1; j<=frog[i].deg; ++j){
            if(i+j>=n || frog[i+j].deg==0) return 0;
            --frog[i+j].deg;
            ans[frog[i].pos][frog[i+j].pos]=ans[frog[i+j].pos][frog[i].pos]=1;
        }
    }
    return 1;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0; i<n; ++i){
            scanf("%d",&frog[i].deg);
            frog[i].pos=i;
        }
        memset(ans,0,sizeof(ans));
        if(Havel()){
            puts("YES");
            for(int i=0; i<n; ++i){
                for(int j=0; j<n; ++j){
                    printf("%d ",ans[i][j]);
                }
                putchar('
');
            }
        }else{
            puts("NO");
        }
        putchar('
');
    }
    return 0;
}