题目

Description

未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)
如果湖泊Li和Lj之间有水路相连,则青蛙Fi和Fj互称为邻居
现在已知每只青蛙的邻居数目x1, x2, ..., xn,请你给出每两个湖泊之间的相连关系

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)
每组数据包括两行,第一行是整数N(2 < N < 10),第二行是N个整数,x1, x2,..., xn(0 ≤ xi ≤ N)

Output

对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"
否则输出"YES",并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0
每两个数字之间输出一个空格
如果存在多种可能,只需给出一种符合条件的情形
相邻两组测试数据之间输出一个空行

Sample Input

3
7
4 3 1 5 4 2 1
6
4 3 1 4 2 0
6
2 3 1 1 2 1

Sample Output

YES
0 1 0 1 1 0 1
1 0 0 1 1 0 0
0 0 0 1 0 0 0
1 1 1 0 1 1 0
1 1 0 1 0 1 0
0 0 0 1 1 0 0
1 0 0 0 0 0 0

NO

YES
0 1 0 0 1 0
1 0 0 1 1 0
0 0 0 0 0 1
0 1 0 0 0 0
1 1 0 0 0 0
0 0 1 0 0 0

题解

有 Havel-Hakimi定理

给定一个非负整数序列{dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化
进一步,若图为简单图,则称此序列可简单图化
可图化的判定：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个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况

简单来说就是从多到少开始尽可能多的连接
用一个 优先队列 维护当前状态下还能连接的个数最多的点

虽然当时不知道这个定理,但是感觉这样是对的……

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
using namespace std;

const int maxn = 15;

struct naive {
    int n;
    int f;
    bool operator < (const naive &rhs)const {
        return f < rhs.f;
    }
};

bool Map[maxn][maxn];

priority_queue <naive> Q1;
queue<naive> Q2;

void Do() {
    int n;
    cin >> n;

    while(!Q1.empty()) Q1.pop();
    while(!Q2.empty()) Q2.pop();
    bool flag = false;
    memset(Map,false,sizeof(Map));

    for(int i = 0;i < n;i++) {
        naive t;
        cin >> t.f;
        t.n = i;
        Q1.push(t);
    }

    while(!Q1.empty()) {
        naive qu = Q1.top();
        Q1.pop();
        while(!Q1.empty() && qu.f > 0) {
            naive qv = Q1.top();
            Q1.pop();
            if(qv.f == 0)
                continue;

            int u = qu.n;
            int v = qv.n;
            if(Map[u][v] == false) {
                Map[u][v] = Map[v][u] = true;
                qu.f--;
                qv.f--;
            }
            if(qv.f > 0)
                Q2.push(qv);
        }
        if(qu.f > 0) {
            flag = true;
            break;
        }
        while(!Q2.empty()) {
            Q1.push(Q2.front());
            Q2.pop();
        }
    }

    if(flag) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++) {
                if(j != 0)
                    cout << " ";
                cout << Map[i][j] ? 1 : 0;

            }
            cout << endl;
        }
    }
}

int main(){
    int T;
    cin >> T;
    while(T--) {
        Do();
        if(T)
            cout << endl;
    }

    return 0;
}