POJ 1659 Frogs' Neighborhood
分析:切图论切的第一道题、也是图论的例题、主要用到一个Havel-Hakimi 定理有以下两种不合理的情形:
(1) 某次对剩下序列排序后,最大的度数(设为d1)超过了剩下的顶点数;
(2) 对最大度数后面的d1 个度数各减1 后,出现了负数。
#include<stdio.h> #include<stdlib.h> #include<string.h> #define N 15 struct vertex{ int degree;//顶点的度 int index;//顶点序号 }v[N]; int cmp(const void *a,const void *b){ return ((vertex*)b)->degree-((vertex*)a)->degree; } int main(){ int t,n,i,j,k,r,p,q,d1; int Edge[N][N],flag; scanf("%d",&t); while(t--){ scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&v[i].degree); v[i].index=i; } memset(Edge,0,sizeof(Edge)); flag=1; for(k=0;k<n&&flag;k++){ qsort(v+k,n-k,sizeof(vertex),cmp); i=v[k].index; d1=v[k].degree; if(d1>n-k-1)flag=0; for(r=1;r<=d1&&flag;r++){ j=v[k+r].index; if(v[k+r].degree<=0)flag=0; v[k+r].degree--; Edge[i][j]=Edge[j][i]=1; } } if(flag){ puts("YES"); for(p=0;p<n;p++){ for(q=0;q<n;q++){ if(q)printf(" "); printf("%d",Edge[p][q]); } puts(""); } } else puts("NO"); if(t) puts(""); } return 0; }
补充:软件开发 , C++ ,