poj 1659 Frogs' Neighborhood 度序列可图化 贪心
2023-09-11 14:20:46 时间
题意:
对一个无向图给出一个度序列,问他是否可简单图化。
分析:
依据Havel定理,直接贪心就可以。
代码:
//poj 1659 //sep9 #include <iostream> #include <algorithm> using namespace std; struct Node{ int num,ids; }p[16]; int ans[16][16]; int n; int cmp(Node a,Node b){ return a.num>b.num; } int main() { int i,j,cases; scanf("%d",&cases); while(cases--){ memset(ans,0,sizeof(ans)); scanf("%d",&n); for(i=1;i<=n;++i){ int d; scanf("%d",&d); p[i].num=d; p[i].ids=i; } int ok; while(1){ sort(p+1,p+1+n,cmp); if(p[1].num==0){ ok=1; break; } int d=p[1].num,u=p[1].ids; p[1].num=0; if(d>n-1){ ok=0; break; } int err=0; for(i=2;i<d+2;++i){ --p[i].num; if(p[i].num<0){ err=1; break; } ans[u][p[i].ids]=1; ans[p[i].ids][u]=1; } if(err==1){ ok=0; break; } } if(ok==0) printf("NO\n\n"); else{ printf("YES\n"); for(i=1;i<=n;++i){ for(j=1;j<=n;++j) printf("%d ",ans[i][j]); printf("\n"); } printf("\n"); } } }
相关文章
- shell中>/dev/null 2>&1
- [React] Recompose: Override Styles & Elements Types in React
- 华为OD机试 - 找到比自己强的人数(Java & JS & Python)
- AGI:走向通用人工智能的【生命学&哲学&科学】第一篇——生命、意识、五行、易经、量子
- 【鲁棒优化、大M法、C&CG算法】计及风、光、负荷不确定性两阶段鲁棒优化(Matlab代码实现)
- 从四个问题透析Linux下C++编译&链接
- 使用set集合去除重复元素&@EqualsAndHashCode注解
- struts1吊牌<logic:iterate>
- 学习C++:C++基础(三)泛型编程&C++模板