首页 > 代码库 > poj 1659 Frogs' Neighborhood (构图)

poj 1659 Frogs' Neighborhood (构图)

2024-07-15 14:15:19   221人阅读

Frogs‘ Neighborhood
Time Limit: 5000MS Memory Limit: 10000K
Total Submissions: 7237 Accepted: 3123 Special Judge

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

374 3 1 5 4 2 1 64 3 1 4 2 0 62 3 1 1 2 1

Sample Output

YES0 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 NOYES0 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 


         正在学习图论当中，一道简单的构图题就把我弄死了一天，最后还是因为输出格式的原因吧。
         解题思路：就是对节点的度进行排序，1.某次对剩下的序列排序后，最大的度数超过剩下的点数。 2.对最大的度数后面节点的度减1，若出现负数。这2种都是不可取的情况。

贴出代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>struct Node{    int index;    int degree;};struct Node node[15];int map[15][15];int cmp(const void * a, const void * b){    return (*(struct Node *)b).degree > (*(struct Node *)a).degree;}int main(){    int mark;    int n, T;    scanf("%d", &T);    while(T--)    {        mark = 1;        memset(map, 0, sizeof(map));        scanf("%d", &n);        for(int i = 1; i<=n; i++)        {            scanf("%d", &node[i].degree);            node[i].index = i;        }        for(int i = 1; i<=n && mark; i++)        {            qsort(node+i, n+1-i, sizeof(node[0]), cmp);   //对剩下的排序            int k = node[i].degree;            int x = node[i].index;            if(k > n-i)      //若出现度数大于后面节点个数就不可以                mark = 0;            for(int j = 1; j<=k && mark; j++)            {                if(node[i+j].degree <= 0)                {                    mark = 0;                    break;                }                node[i+j].degree--;                int y = node[i+j].index;                map[x][y] = map[y][x] = 1;            }        }        if(!mark)            printf("NO\n");        else        {           printf("YES\n");            for(int i=1;i<=n;i++)            {                for(int j=1;j<n;j++)                    printf("%d ",map[i][j]);                printf("%d",map[i][n]);               printf("\n");            }        }        printf("\n");    }    return 0;}

 


联系
我们