题解 | 小红的二分图构造

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();
            String[] s = in.nextLine().split(" ");
            int[] degree = Arrays.stream(s).mapToInt(Integer::parseInt).toArray();
            int sum = 0;
            for (int i : degree) {
                sum += i;
            }
            //构成二分图的必要方案是度数和必须为偶数（因为每一条边都会连接两个值会产生2度数）
            if (sum % 2 != 0) {
                System.out.println(-1);
                continue;
            }
            //初始化二分图
            List<Integer>[] graph = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }
            //分组数组，true表示该索引属于u分组，false属于v分组
            boolean[] belongsToU = new boolean[n]; 
            //动态规划划分分组，bp[i][j]表示用前i个degree能够获取得到和为j的子集吗
            int average = sum / 2;
            boolean[][] dp=new boolean[n+1][average+1];
                //当j为0时总是能够得到子集的
            for(int i=0;i<n+1;i++){
                dp[i][0]=true;
            }
            for(int i=1;i<=n;i++){
                for(int j=1;j<=average;j++){
                    //沿用i-1时的方案，即放弃i
                    dp[i][j]=dp[i-1][j];
                    //使用i，如果dp[i-1][j-degree[i-1]]可行的话，加上degree[i-1]刚好等于j
                    if(j>=degree[i-1])dp[i][j]|=dp[i-1][j-degree[i-1]];
                }
            }
            //无法划分为两组度数和相等的子集则表示无法构造二分图
            if (!dp[n][average]) { 
                System.out.println(-1);
                continue;
            }
            //回溯dp生成划分方案
            int temp=average;
            for(int i=n;i>0;i--){
                //每次只寻找必须用到的i，即dp[i][temp]可构成且不是从i-1沿用过来的
                if(dp[i][temp]&&!dp[i-1][temp]){
                    belongsToU[i-1]=true;
                    temp-=degree[i-1];
                }
            }
            //构造边
                //剩余度数
            int[] restOfDegree = degree.clone();
            for (int i = 0; i < n; i++) {
                //只在u上构建边（因为每次构建都会连接u和v）
                if (belongsToU[i]) {
                    //当前u和v都有度数剩余则直接创建，否则遍历下一个v或者进入下一个u
                    for (int j = 0; j < n && restOfDegree[i] > 0; j++) {
                        while(!belongsToU[j] && restOfDegree[j] > 0&& restOfDegree[i] > 0) {
                            graph[i].add(j);
                            graph[j].add(i);
                            restOfDegree[j]--;
                            restOfDegree[i]--;
                        }
                    }
                }
            }
            System.out.println(average);
            for (int i = 0; i < n; i++) {
                for (int j : graph[i]) {
                    if (belongsToU[i])System.out.println((i + 1) + " " + (j + 1));
                }
            }


        }
    }
}