POJ 1659 Frogs' Neighborhood

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 

Suggest Answer

这道题就是给出图的所有顶点的度数,判定图的可图性,并且构建该无向图的关联矩阵,用到的是Havel–Hakimi定理

Havel–Hakimi定理:令S=(d1,d2,…,dn-1,dn)为有限多个非负整数组成的非递增序列.S可简单图化当且仅当有穷序列S’=(d2-1,d3-1,…,dn)只含有非负整数且是可简单图化的.

其次是要注意输出格式,我就因为输出格式错误WA了两次

public class _1659 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        listCompare c = new listCompare();
        int T = input.nextInt();
        for (int i = 0; i < T; i++) {
            int N = input.nextInt();
            List<Integer[]> list = new ArrayList<Integer[]>();
            int[][] arr = new int[N][N];
            Boolean hasNegetive = false;
            for (int j = 0; j < N; j++) {
                int num = input.nextInt();
                Integer[] t = { j, num };
                list.add(t);
            }
            Collections.sort(list, c);
            while (list.get(0)[1] > 0) {
                int first = list.get(0)[1];
                int index = list.get(0)[0];
                for (int j = 1; j <= first; j++) {
                    int tempindex = list.get(j)[0];
                    int v = list.get(j)[1] - 1;
                    Integer[] temparr = { tempindex, v };
                    list.set(j, temparr);
                    arr[index][tempindex] = 1;
                    arr[tempindex][index] = 1;
                }
                Integer[] tarr = { index, 0 };
                list.set(0, tarr);
                Collections.sort(list, c);
            }
            for (int j = 0; j < list.size(); j++) {
                if (list.get(j)[1] < 0) {
                    hasNegetive = true;
                }
            }
            if (hasNegetive == true) {
                System.out.println("NO");
                System.out.println();
            } else {
                System.out.println("YES");
                for (int[] row : arr) {
                    for (int col : row) {
                        System.out.print(col + " ");
                    }
                    System.out.println();
                }
                System.out.println();
            }
        }
        input.close();
    }
}

class listCompare implements Comparator<Integer[]> {
    @Override
    public int compare(Integer[] o1, Integer[] o2) {
        if (o1[1] < o2[1]) {
            return 1;
        } else if (o1[1] > o2[1]) {
            return -1;
        } else {
            return 0;
        }
    }
}