POJ 1659 Frogs' Neighborhood(度序列构图)

Posted on In ,

题意 中文

根据Havel-Hakimi定理构图就行咯 先把顶点按度数从大到小排序 可图的话 度数大的顶点与它后面的度数个顶点相连肯定是满足的 出现了-1就说明不可图了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
int mat[N][N], ord[N];

bool cmp(int i, int j)
{
    return mat[i][0] > mat[j][0];
}

int main()
{
    int cas, i, j, k, t, n;
    scanf("%d", &cas);
    while(cas--)
    {

        memset(mat, 0, sizeof(mat));
        scanf("%d", &n);
        for(i = 1; i <= n; ++i)
        {
            scanf("%d", &mat[i][0]);
            ord[i] = i;
        }

        for(i = 1; i <= n; ++i)
        {
            sort(ord + i, ord + n + 1, cmp);
            t = ord[i];
            if(mat[t][0] < 0) break;
            for(j = 1; j <= mat[t][0]; ++j)
            {
                k = ord[i + j];
                mat[t][k] = mat[k][t] = 1;
                --mat[k][0];
            }
        }

        if(i <= n) printf("NO\n");
        else
        {
            printf("YES\n");
            for(i = 1; i <= n; ++i)
            {
                for(int j = 1; j <= n; ++j)
                    printf("%d ", mat[i][j]);
                printf("\n");
            }
        }
        if(cas) printf("\n");
    }
    return 0;
}

Frogs’ Neighborhood

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

Source

POJ Monthly–2004.05.15 Alcyone@pku