Frogs' Neighborhood
未名湖附近共有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
题目类型：Havel-Hakimi算法
算法分析：按照所给的点的度数来判断是否能够组成一个图，可以直接使用Havel-Hakimi算法来计算
|
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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> using namespace std; const int maxn = 36; int edge[maxn][maxn]; struct Node { int v, id; }; Node input[maxn]; bool is_valid; int n; bool Cmp (Node a, Node b) { return a.v > b.v; } void Solve () { int i; for (i = 0; i < n; i++) { sort (input + i, input + n, Cmp); if (input[i].v > n - i - 1) { is_valid = false; return ; } int j; for (j = i + 1; j < i + 1 + input[i].v; j++) { input[j].v--; if (input[j].v < 0) { is_valid = false; return ; } edge[input[i].id][input[j].id] = edge[input[j].id][input[i].id] = 1; } } } int main() { // ifstream cin ("aaa.txt"); int t; cin >> t; while (t--) { cin >> n; int i; for (i = 0; i < n; i++) { cin >> input[i].v; input[i].id = i; } memset (edge, 0, sizeof (edge)); is_valid = true; Solve (); if (is_valid) { cout << "YES" << endl; int j; for (i = 0; i < n; i++) { for (j = 0; j < n - 1; j++) cout << edge[i][j] << " "; cout << edge[i][j] << endl; } } else cout << "NO" << endl; cout << endl; } return 0; } |
- « 上一篇：poj1651
- poj1679：下一篇 »