首页 > 代码库 > poj1659Havel-hakimi 定理

poj1659Havel-hakimi 定理

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;struct Node{    int x;int val;}node[100];int cmp(const Node &a,const Node &b){    return a.val>b.val;}int G[100][100];int main(){    int t,n;    cin>>t;    int cc=t;    while(t--){        memset(G,0,sizeof(G));        cin>>n;        for(int i=0;i<n;i++){            int c;cin>>c;            node[i].x=i;node[i].val=c;        }        bool flag=true;        for(int i=0;i<n&&flag;i++){            sort(node+i,node+n,cmp);            for(int j=1;j<=node[i].val;j++){                int k=i+j;                if(k>=n){                    flag=false;break;                }                node[k].val--;                if(node[k].val<0){                    flag=false;break;                }                G[node[i].x][node[k].x]=1;                G[node[k].x][node[i].x]=1;            //    cout<<node[i].x<<" "<<node[k].x<<endl;            //    system("pause");            }        }        if(!flag){            if(t!=cc-1) cout<<endl;            cout<<"NO"<<endl;        }        else{            if(t!=cc-1) cout<<endl;            cout<<"YES"<<endl;            for(int i=0;i<n;i++){                for(int j=0;j<n;j++){                    if(j==0) cout<<G[i][j];                    else cout<<" "<<G[i][j];                }                cout<<endl;            }        }    }    return 0;}