题解 | 小红的二分图构造

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class hj118 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] degree = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            degree[i] = scanner.nextInt();
            sum += degree[i];
        }
        if ((sum & 1) == 1) {
            System.out.print(-1);
            return;
        }

        int target = sum / 2;

        boolean[] dp = new boolean[target + 1];
        int[] prev = new int[target + 1];
        Arrays.fill(prev, -1);
        dp[0] = true;
        for (int i = 0; i < n && !dp[target]; i++) {
            for (int j = target; j >= degree[i] && !dp[target]; j--) {
                if (dp[j - degree[i]]) {
                    dp[j] = true;
                    prev[j] = i;
                    break;          //这个break必须要，防止替换掉之前的
                }
            }
        }
        if (!dp[target]) {
            System.out.print(-1);
            return;
        }
        System.out.println(sum / 2);
        ArrayList<Integer> vertex1 = new ArrayList<>();
        ArrayList<Integer> vertex2 = new ArrayList<>();
        for (int i = target; i > 0; i -= degree[prev[i]]) {
            if (!vertex1.contains(prev[i])) {
                vertex1.add(prev[i]);
            }
        }
//        for(int i = 0; i < prev.length;i++)
//            System.out.print(String.valueOf(prev[i])+" ");
        for (int i = 0; i < n; i++) {
            if (!vertex1.contains(i)) vertex2.add(i);
        }
        System.out.println(vertex1);
        System.out.println(vertex2);
        for (int i = 0; i < vertex1.size(); i++) {
            int v1 = vertex1.get(i);
            for (int j = 0; j < vertex2.size() && degree[v1] > 0; j++) {
                int v2 = vertex2.get(j);
                if (degree[v2] > 0) {

                    System.out.print(Math.min(v1, v2) + 1);
                    System.out.print(" ");
                    System.out.println(Math.max(v1, v2) + 1);
                    degree[v1]--;
                    degree[v2]--;
                }
            }
        }
    }
}