POJ - Frogs' Neighborhood(Havel-Hakimi)
发布日期:2021-07-01 00:16:14
浏览次数:2
分类:技术文章
本文共 1985 字,大约阅读时间需要 6 分钟。
题目链接:
Time Limit: 5000MS | Memory Limit: 10000K |
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 0NO
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
Problem solving report:
Description: 有n个点,给出n个点分别与其它几个点相连,输出他们的相连关系图。
Problem solving: havel-hakimi定理()。#include#include #include using namespace std;struct vertex { int index; int degree;}v[15];int n, map[15][15];bool cmp(struct vertex A, struct vertex B) { return A.degree > B.degree;}bool Havel() { for (int i = 0; i < n - 1; i++) { sort(v + i, v + n, cmp); int t1 = v[i].index; for (int j = i + 1; j <= i + v[i].degree; j++) { v[j].degree--; if (v[j].degree < 0) return false; int t2 = v[j].index; map[t1][t2] = map[t2][t1] = 1; } } if (v[n - 1].degree) return false; return true;}int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); memset(map, 0, sizeof(map)); for (int i = 0; i < n; i++) { v[i].index = i; scanf("%d", &v[i].degree); } if (Havel()) { printf("YES\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%d ", map[i][j]); printf("\n"); } } else printf("NO\n"); if (t) printf("\n"); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/86664711 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月22日 10时47分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
正则表达式简介(微软)--4.正则表达式语法
2019-05-01
正则表达式简介(微软)--5.建立正则表达式
2019-05-01
正则表达式简介(微软)--6.优先权顺序
2019-05-01
算法-Hash+滑动窗口/按位编码-重复的DNA序列
2019-05-01
多用户与多租户的区别
2019-05-01
算法-滑动窗口-最小覆盖子串
2019-05-01
算法-图/DFS/BFS/并查集-岛屿数量
2019-05-01
算法-并查集
2019-05-01
常使用的Emacs命令
2019-05-01
现代UNIX系统有什么设计上的不足么
2019-05-01
wait3,wait4 用法
2019-05-02
服务器TIME_WAIT和CLOSE_WAIT详解和解决办法
2019-05-02
使用gprof来对程序的性能分析总结
2019-05-02
Python3中的Bytes和str之间的关系
2019-05-02
Python自动化运维 - day3 - 文件处理 - 函数part1
2019-05-02
Python自动化运维 - day14 - JavaScript基础
2019-05-02
oracle保存小数点前为"0"的问题
2019-05-02
linux sar 命令详解
2019-05-02
LINUX 使用管道实现无需落地文件GZIP压缩
2019-05-02