link:http://poj.org/problem?id=1659
其实就是已知多少点,且知道每个点所对应的连的点数(度数),问这样情况是神马~~~
用到Havel-kakimi定理;
1) 某次排列后,最大的度数超过了剩下的顶点数
2) 最大度数后面dl个度数各减一后,出现负数
一旦出现上述情况,说明该序列不可图
code:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 15

using namespace std;

typedef struct node
{
    int degree;
    int num;
}node;
node p[N];
int visit[N][N];

bool cmp(node a,node b)
{
    return a.degree>b.degree;
}

int main()
{
    int t,n;
    int i,j,flag;
    scanf("%d",&t);
    while(t--)
    {
        flag=1;
        scanf("%d",&n);
        memset(visit,0,sizeof(visit));

        for(i=1;i<=n;i++)
        {
            scanf("%d",&p[i].degree);
            p[i].num=i;
        }

        for(i=1;i<=n;i++)
        {
            sort(p+i,p+n+1,cmp);
            for(j=1;j<=p[i].degree;j++)
            {
                visit[p[i].num][p[i+j].num]=visit[p[i+j].num][p[i].num]=1;
                p[i+j].degree--;
                if(p[i+j].degree<0)
                {
                    flag=0;
                    break;
                }
            }
            if(flag==0)
                break;
        }
        if(!flag)
            printf("NO\n");
        else
        {
            printf("YES\n");
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    printf("%d",visit[i][j]);
                    if(j!=n)
                        printf(" ");
                }
                printf("\n");
            }
        }
        if(t)
            printf("\n");
    }
    return 0;
}

用Havel-kakimi定理,并在构图中判断是否出现不合理的地方:

1)           某次排列后,最大的度数(dl)超过了剩下的顶点数

2)           最大度数后面dl个度数各减一后,出现负数

用Havel-kakimi定理,并在构图中判断是否出现不合理的地方:

1)           某次排列后,最大的度数(dl)超过了剩下的顶点数

2)           最大度数后面dl个度数各减一后,出现负数

发表评论

电子邮件地址不会被公开。

Post Navigation