首页 > 代码库 > poj 1659 Frogs' Neighborhood (Havel-Hakimi定理,判断序列是否可图)
poj 1659 Frogs' Neighborhood (Havel-Hakimi定理,判断序列是否可图)
链接:poj 1659
中文题不必解释题意、、、
其实质是给定一个度序列,判断是否可图,
若可图,输出YES,并输出各顶点之间的连边的情况
否则,输出NO
思路:判断一个序列是否可图,直接利用Havel-Hakimi定理即可
判断任意一个序列是否可图的具体过程:
(1)先将序列由大到小排序
(2)设最大的度数为 t ,将最大项删除,然后把最大度数后
(不包括自己)的 t 个度数分别减1(意思就是把度数最大的点与后几个点连边)
(3)重复上述两步,如果最大度数t超过了剩下顶点的个数,
或者序列中出现了负数,则不可图,如果序列全部变为0,则可图。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct stu { int d,id; }frog[12]; int cmp(struct stu a,struct stu b) { return a.d>b.d; } int main() { int T,n,i,pos,j,k,edge[12][12],flag; scanf("%d",&T); while(T--){ scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&frog[i].d); frog[i].id=i; } memset(edge,0,sizeof(edge)); flag=1; pos=1; while(1){ sort(frog+pos,frog+1+n,cmp); //先由大到小排序 k=frog[pos].d; //找到最大项 if(k==0) //若最大项为0,则序列全部为0 break; if(pos+k>n){ //若最大度数超过了顶点的个数则不合理 flag=0; break; } for(i=pos+1;i<=pos+k;i++){ //对最大项后的k项依次减一 frog[i].d--; edge[frog[pos].id][frog[i].id]=1; edge[frog[i].id][frog[pos].id]=1; if(frog[i].d<0){ //判断是否出现负度数 flag=0; break; } } pos++; } if(!flag) printf("NO\n"); else{ printf("YES\n"); for(i=1;i<=n;i++) for(j=1;j<=n;j++){ printf("%d",edge[i][j]); if(j==n) printf("\n"); else printf(" "); } } if(T) printf("\n"); } return 0; }
poj 1659 Frogs' Neighborhood (Havel-Hakimi定理,判断序列是否可图)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。