admin管理员组文章数量:1602097
题目:已知一个无向图的所有顶点的度,问能否构造成一个简单图。
分析:图论。使用Havel定理或者Erdős定理。
构成图判定:所有点的度数和为偶数(防止溢出可以只判断奇偶);
构成简单图:
1.Havel定理:将所有边排序,将度数最大的顶点依次与剩下的顶点连接边(从度数大的开始),
去掉度数最大的顶点后构成子问题,如果出现矛盾则失败,否则成功;
(通过贪心证明);
2.Erdős定理:
说明:好几道题都卡了很久:-(。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int degrees[10005];
bool cmp(int a, int b)
{
return a > b;
}
int havel_hakimi(int n)
{
for (int i = 0; i < n; ++ i) {
sort(degrees+i, degrees+n, cmp);
for (int j = i+1; j < n && degrees[i]; ++ j) {
degrees[j] --;
degrees[i] --;
if (degrees[j] < 0) {
return 0;
}
}
if (degrees[i]) {
return 0;
}
}
return 1;
}
int main()
{
int n;
while (~scanf("%d",&n) && n) {
int flag = 0;
for (int i = 0; i < n; ++ i) {
scanf("%d",°rees[i]);
if (degrees[i] < 0) {
flag = 1;
}
}
int sum = 0;
for (int i = 0; i < n; ++ i) {
sum += degrees[i];
sum %= 2;
}
if (flag || sum % 2) {
puts("Not possible");
}else {
// Havel-Hakimi
if (!havel_hakimi(n)) {
puts("Not possible");
}else {
puts("Possible");
}
}
}
return 0;
}
本文标签: uvaconstructionGraph
版权声明:本文标题:UVa 10720 - Graph Construction 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728396669a1157087.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论