题解 | 小红的二分图构造

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solved() {
    int n; // 节点数量
    cin >> n; // 读取节点数量
    vector<int> d(n + 1); // 存储每个节点的度数，数组大小为 n+1，方便从1开始索引

    int sum = 0; // 用于存储所有节点度数的总和
    for (int i = 1; i <= n; i++) { // 读取每个节点的度数
        cin >> d[i]; // 输入第i个节点的度数
        sum += d[i]; // 累加度数总和
    }

    if (sum & 1) { // 特判：如果度数总和是奇数，无法构造二分图
        cout << -1; // 输出-1表示无解
        return; // 退出函数
    }

    // 动态规划部分，使用01背包思想
    // 定义状态f[i][j]：前i个节点中，选择一些节点，使得它们的度数和恰好为j的最多个数
    // ff数组用来跟踪解，ff[i][j]：当前的f[i][j]是否选了第i个数(0表示没选,1表示选了)
    vector<vector<int>> f(n + 1, vector<int>(sum / 2 + 1, -1e9)); // 初始化f数组，初始值为一个很大的负数
    vector<vector<int>> ff(n + 1, vector<int>(sum / 2 + 1, 0)); // 初始化ff数组，初始值为0
    for (int i = 0; i <= n; i++) f[i][0] = 0; // 当度数和为0时，选择数量为0

    for (int i = 1; i <= n; i++) { // 遍历每个节点
        for (int j = 1; j <= sum / 2; j++) { // 遍历每个可能的度数和
            if (j >= d[i] && f[i - 1][j] <= f[i - 1][j - d[i]] + 1) { // 如果当前节点可以加入集合，并且选择它更优
                f[i][j] = f[i - 1][j - d[i]] + 1; // 更新f数组，选择当前节点
                ff[i][j] = 1; // 标记选择状态为1，表示选择了当前节点
            } else {
                f[i][j] = f[i - 1][j]; // 不选择当前节点，继承上一个状态
            }
        }
    }

    int cnt = 0; // 用于存储边的数量
    vector<int> l, r; // 用于存储两个集合的节点
    if (f[n][sum / 2] <= 0) { // 如果无法找到一种组合使得度数和为sum/2
        cout << -1; // 输出-1表示无解
        return; // 退出函数
    } else { // 如果有解
        int now = sum / 2; // 当前目标度数和
        for (int i = n; i >= 1; i--) { // 跟踪解
            if (ff[i][now]) { // 如果选择了当前节点
                l.push_back(i); // 将当前节点加入集合l
                now -= d[i]; // 更新当前目标度数和
                cnt += d[i]; // 累加边的数量
            } else {
                r.push_back(i); // 否则将当前节点加入集合r
            }
        }
    }

    cout << cnt << '\n'; // 输出边的数量
    for (int lx : l) { // 遍历集合l中的每个节点
        for (int rx : r) { // 遍历集合r中的每个节点
            int z = min(d[lx], d[rx]); // 计算两个节点之间可以连接的边数
            d[lx] -= z; // 更新集合l中节点的剩余度数
            d[rx] -= z; // 更新集合r中节点的剩余度数
            while (z--) cout << lx << ' ' << rx << '\n'; // 输出每条边
        }
    }
}

int main() {
    solved(); // 调用solved函数
    return 0;
}