HDU 2454 Degree Sequence of Graph G——可简单图化&&Heavel定理
amp 简单 of HDU sequence Graph 定理
2023-09-27 14:27:45 时间
题意
给你一个度序列,问能否构成一个简单图。
分析
对于可图化,只要满足度数之和是偶数,即满足握手定理。
对于可简单图化,就是Heavel定理了。
Heavel定理:把度序列排成不增序,即 $deg[1] \geq deg[2] \geq ... \geq deg[V]$,则 $deg$ 可简单图化当且仅当 ${deg}' = \{deg[2]-1, deg[3]-1,...,deg[deg[1]+1]-1,...,deg[v] \}$ 可简单图化。
简单地说,把 $deg$ 从大到小排序后,找出度最大的点(设度为$d$),将它与度次大的 $d$ 的点连边,然后这个点就可以不管了。一直重复这个过程,直到用完所有的点。如果中间出现负度或剩下节点数小于当前节点的度数,则说明不可简单图化。(其实还是在运用握手定理)
#include<bits/stdc++.h> using namespace std; const int maxn = 1000 + 10; int n, a[maxn]; int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i = 0;i < n;i++) scanf("%d", &a[i]); bool flag = false; for(int i = 0;i < n;i++) { sort(a+i, a+n, greater<int>()); if(a[i] < 0 || a[i] > n-1-i) { flag = true; break; } for(int j = 1;j <= a[i];j++) a[i+j]--; } if(flag) printf("no\n"); else printf("yes\n"); } return 0; }
参考链接:
1. https://blog.csdn.net/Yasola/article/details/77862481
2. https://blog.csdn.net/shuangde800/article/details/7857246
相关文章
- hdu1025 Constructing Roads In JGShining's Kingdom(二分+dp)
- MyEclipse2014高速配置Spring & Spring Testing, Spring AOP简单使用
- 设计模式之策略模式&简单工厂模式
- POJ--2449--Remmarguts' Date【dijkstra_heap+A*】第K短路
- PHP 性能分析(一): XHProf & XHGui 介绍
- 字典属性化访问Dict2Obj & __setattr__的思考
- java & javaw
- 玩转Kafka—Spring&Go整合Kafka
- 【前端学习之HTML&CSS】-- CSS第一篇 -- 为网页添加样式
- 全面解析 | 钥匙环服务的应用场景&商业价值
- 【Redis入门笔记 05】Jedis 简介 & SpringBoot 集成
- SpringMvc--前端传值&控制器响应
- 百度BML&飞桨训练营(二)基本流程熟悉NLP简单模型训练
- glm编译错误问题解决 formal parameter with __declspec(align('16')) won't be aligned
- Spring -- Bean自己主动装配&Bean之间关系&Bean的作用域
- SVG 剪裁与蒙版(clipPath & mask)