http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=349#problem/A
这道题虽说是图的基础题,但考虑的东西也不少,对于是否可简单图化之前先要判断是否可图化,此题我用Haval定理做的
#include<stdio.h>
#include<string.h>
int neighbor[20][20];//记录邻接矩阵
int frog[20],num[20];//记录度数列与其所在数组下标
int main(){
    int m;
    scanf("%d",&m);
    while(m–){//先用后减一
        int n,i,j,flag=1;
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&frog[i]);
            num[i]=i;
        }
        memset(neighbor,0,sizeof(neighbor));//将neighbor数组清零
        while(1){
            int end=1;
            for(i=1;i<=n;i++)
                if(frog[i]!=0){//检查该度数列经过计算后是否全为零
                    end=0;
                    break;
                }
            if(end){
                flag=1;
                break;
            }
            int t=0;
            for(i=1;i<n;i++){//冒泡法排序并交换num中位置的数据
               for(j=n;j>=2;j–){
                    if(frog[j]>frog[j-1]){
                        t=frog[j-1];
                        frog[j-1]=frog[j];
                        frog[j]=t;
                        t=num[j-1];
                        num[j-1]=num[j];
                        num[j]=t;
                    }
                }
            }
            t=0;
            for(i=1;i<=n;i++)//记录度数列中大于零的数据个数
                if(frog[i]>0)
                    t++;
            if(t-1<frog[1]){//判断是否可图化
               flag=0;
               break;
            }
            i=1;
            while(frog[1]){
                if(frog[i]>0&&num[i]!=num[1]&&neighbor[num[i]][num[1]]==0){
                    frog[i]–;
                    neighbor[num[i]][num[1]]=neighbor[num[1]][num[i]]=1;//利用无向图邻接矩阵的特点
                    frog[1]–;
                }
                i++;
            }
        }
        if(flag){
            printf("YES\n");
            for(i=1;i<=n;i++){
                for(j=1;j<n;j++)
                printf("%d ",neighbor[i][j]);
                printf("%d\n",neighbor[i][n]);
            }
            printf("\n");
        }
        else
        printf("NO\n\n");
    }
    return 0;
} 

发表评论

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

Post Navigation