题目大意:给n个整数, 分别代表图中n个顶点的度,判断是否能构成一张图。

  看到这个题后,除了所有数之和应该为偶数之外,没有别的想法了,只好在网上搜解题报告了。然后了解了Havel-Hakimi定理。之后的事情就简单了。

 #include <cstdio>
#include <algorithm>
#include <functional>
using namespace std; #define MAXN 10000+10 int a[MAXN];
int n; bool Havel_Hakimi()
{
for (int i = ; i < n-; i++)
{
sort(a+i, a+n, greater<int>());
if (i + a[i] >= n) return false;
for (int j = i+; j <= i+a[i]; j++)
{
a[j]--;
if (a[j] < ) return false;
}
}
if (a[n-]) return false;
return true;
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
while (scanf("%d", &n) && n)
{
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
if (Havel_Hakimi()) printf("Possible\n");
else printf("Not possible\n");
}
return ;
}

最新文章

  1. 394. Decode String
  2. 分类指标准确率(Precision)和正确率(Accuracy)的区别
  3. 求三数中Max和猜拳游戏
  4. php apc
  5. Python学习教程(learning Python)--1.1Python程序设计流程
  6. 使用 sp_executesql
  7. VMware 虚拟机安装 Mac OS X Mountain Lion 苹果系统
  8. Android Monkey
  9. 趣味算法——青蛙过河(JAVA)
  10. Android(性能)
  11. activiti笔记二:用户任务
  12. PHP导入导出Excel方法
  13. js面向对象学习笔记(四):对象的混合写法
  14. 雷林鹏分享:jQuery EasyUI 数据网格 - 创建复杂工具栏
  15. [转] The QCOW2 Image Format
  16. tp5.0 SHOW COLUMNS FROM 生成数据表字段缓存
  17. 矩形A + B HDU2524
  18. ftp下载文件失败get: Access failed: 550 Failed to open file. (t1.log)
  19. Linux快速安装apache+mysql+php环境
  20. 蓝绿部署、红黑部署、AB测试、灰度发布、金丝雀发布、滚动发布的概念与区别(转)

热门文章

  1. Oracle数据库设计小细节
  2. mysql 创建数据 utf8
  3. LDA,PCA阅读资料
  4. 模态对话框 bootstrap-modal.js
  5. jsp 获取cookie 的值的方法
  6. Sybase数据库的分页功能
  7. 阿里笔试js题
  8. NanoApe Loves Sequence Ⅱ(尺取法)
  9. armstrong&#39;s programming erlang 2nd
  10. LaTeX 多个图片共用一个题注的实现--子图形