首页 > 代码库 > POJ 1659 Frogs' Neighborhood 可图性判断-Havel定理

POJ 1659 Frogs' Neighborhood 可图性判断-Havel定理

2024-11-01 20:30:02   210人阅读

Description

未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖)，每个湖泊Li里住着一只青蛙Fi(1 ≤i ≤ N)。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1,x2, ..., xn，请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，第一行是整数N(2 < N < 10)，第二行是N个整数，x1,x2,..., xn(0 ≤ xi ≤ N)。

Output

对输入的每组测试数据，如果不存在可能的相连关系，输出"NO"。否则输出"YES"，并用N×N的矩阵表示湖泊间的相邻关系，即如果湖泊i与湖泊j之间有水路相连，则第i行的第j个数字为1，否则为0。每两个数字之间输出一个空格。如果存在多种可能，只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

Sample Input

3
7
4 3 1 5 4 2 1 
6
4 3 1 4 2 0 
6
2 3 1 1 2 1

Sample Output

YES
0 1 0 1 1 0 1 
1 0 0 1 1 0 0 
0 0 0 1 0 0 0 
1 1 1 0 1 1 0 
1 1 0 1 0 1 0 
0 0 0 1 1 0 0 
1 0 0 0 0 0 0 

NO

YES
0 1 0 0 1 0 
1 0 0 1 1 0 
0 0 0 0 0 1 
0 1 0 0 0 0 
1 1 0 0 0 0 
0 0 1 0 0 0 题目的要求是根据一组给定的度数列 能否构成一幅完整的图 如果可以则输出图的邻接矩阵；根据Havel定理 可知：如果最大度数顶点的度数大于其他所有顶点个数之和，则不能构成图。
这样我们可以每次
1 对度数数组进行排序
2 根据定理判断能否构图
3 每次完成一个最大度数点的连通（去掉该点，并让后面Dmax个顶点的度数减1）
重复上述步骤 即可完成构图


代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int num;       //编号
    int degree;    
} q[20];
int map[20][20];     //邻接矩阵
int s;
int cmp(node a,node b)
{
    return a.degree>b.degree;      //根据度数从大到小排序
}
void connect()              //连通度数最大的点
{
    int a,b;
    int j=2;
    a=q[1].num;
    while(q[1].degree--)      //Dmax个顶点度数-1
    {
        b=q[j].num;
        q[j].degree--;
        if(q[j].degree==0)  // 某个点度数为0 则剩下顶点数量-1
            s--;
            j++;
        map[a][b]=map[b][a]=1;  //连通
    }
    return;
}
int main()
{
    int m,n,maxd;
    int i,j,flag;
    int t=0;
    scanf("%d",&n);
    while(n--)
    {
        if(t!=0)
            cout<<endl;
        t++;
        flag=0;
        scanf("%d",&m);
        s=m;
        maxd=0;
        memset(map,0,sizeof(map));
        for(i=1; i<=m; i++)
        {
            scanf("%d",&q[i].degree);
            q[i].num=i;
            if(q[i].degree<=0)
                s--;
            if(q[i].degree>maxd)
                maxd=q[i].degree;
        }
        sort(q+1,q+1+m,cmp);
        while(maxd!=0)
        {
            if(maxd>s-1)                  //定理
            {
                flag=1;
                cout<<"NO"<<endl;
                break;
            }
            sort(q+1,q+1+m,cmp);
            connect();
            s--;                        //去掉度数最大的顶点
            sort(q+1,q+1+m,cmp);
            maxd=q[1].degree;
        }
        if(!flag)
        {
            cout<<"YES"<<endl;
            for(i=1;i<=m;i++)
                for(j=1;j<=m;j++)
                {
                    if(j!=m)
                    cout<<map[i][j]<<' ';
                    else
                    cout<<map[i][j]<<endl;
                }
        }
    }
    return 0;
}



POJ 1659 Frogs' Neighborhood 可图性判断-Havel定理


联系
我们