題目大意：給出無向圖每個(gè)頂點(diǎn)的度，試圖構(gòu)建一個(gè)符合條件的圖。
見Havel-Hakimi定理。
以下是我的代碼：
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(17);
struct Type
{
int num,degree;
};
bool operator<(const Type &a,const Type &b)
{
return (a.degree>b.degree || (a.degree==b.degree && a.num<b.num));
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T;
scanf("%d",&T);
for(int case_num=1;case_num<=T;case_num++)
{
int n;
Type r[kMaxn];
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
r[i].num=i;
scanf("%d",&r[i].degree);
}
bool success(true);
int g[kMaxn][kMaxn];
memset(g,0,kMaxn*kMaxn*sizeof(int));
for(int i=1;i<=n;i++)
{
sort(r+i,r+n+1);
if(r[i].degree<0)
{
success=false;
break;
}
for(int j=i+1;j<=n && j<=i+r[i].degree;j++)
{
g[r[i].num][r[j].num]=g[r[j].num][r[i].num]=1;
r[j].degree--;
}
}
if(case_num!=1)
printf("\n");
if(!success)
printf("NO\n");
else
{
printf("YES\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(j!=1)
printf(" ");
printf("%d",g[i][j]);
}
printf("\n");
}
}
}
return 0;
}
posted on 2011-05-26 13:10
lee1r 閱讀(184)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論