题解 | #小红的二分图构造#

题目链接

题目描述

给定 $N$ 个节点的度数序列 $d_1, d_2, \dots, d_n$ ( $1 \le n \le 100$ , $1 \le d_i \le n-1$ )，要求构造一个含 $N$ 个节点的二分图，使得第 $i$ 个节点的度数恰好为 $d_i$ 。

如果无法构造，输出 -1。否则，输出图的边数和所有边。构造的图可以包含重边，但不能有自环。

解题思路

这是一个构造性问题。解决问题的关键在于理解二分图的度数性质，并将问题分解为两个主要步骤：划分和连接。

1. 核心性质与问题转化

握手定理: 任何图中，所有节点的度数之和等于边数的两倍。因此，如果给定的度数之和 $\sum d_i$ 是奇数，则不可能构成任何图，直接输出 -1。
二分图性质: 在一个二分图的两个点集 $U$ 和 $V$ 中， $U$ 中所有节点的度数之和必须等于 $V$ 中所有节点的度数之和，且这个和等于总边数。 $\sum_{u \in U} \text{deg}(u) = \sum_{v \in V} \text{deg}(v) = \text{总边数}$

结合这两点，我们可以推断出，如果存在一个合法的划分，那么 $U$ 和 $V$ 两部分节点的度数之和都必须恰好是总度数和的一半，即 $\frac{1}{2}\sum d_i$ 。

问题因此转化为：我们能否从给定的 $N$ 个度数中，找出一个子集，使得这个子集的度数之和恰好等于总度数和的一半？

这正是一个经典的子集和问题 (Subset Sum Problem)。

2. 子集和划分 (DP)

我们可以使用动态规划来解决子集和问题。

计算总度数和 $S = \sum_{i=1}^N d_i$ 。若 $S$ 为奇数，则无解。
设定目标和 $T = S / 2$ 。
定义 $dp[i][j]$ 为一个布尔值，表示是否可以用前 $i$ 个节点的度数凑出和为 $j$ 。
状态转移方程为： $dp[i][j] = dp[i-1][j] \lor dp[i-1][j-d_i]$ （即不选第 $i$ 个节点，或者选择第 $i$ 个节点）
如果最终 $dp[N][T]$ 为 false，则说明不存在这样的划分，无解。
如果 $dp[N][T]$ 为 true，我们可以通过回溯 DP 表来构造出两个点集 $U$ 和 $V$ 。

3. 边的构造

在成功将节点划分为 $U$ 和 $V$ 两组后，我们需要在它们之间连边以满足度数要求。由于允许存在重边，我们可以使用一个非常简单且有效的构造方法：

创建两个“端口”列表，u_ports 和 v_ports。
遍历 $U$ 集合中的每个节点 $u$ 。如果其度数为 $d_u$ ，就向 u_ports 列表中添加 $d_u$ 个 $u$ 的 ID。
同样地，遍历 $V$ 集合，为每个节点 $v$ 添加 $d_v$ 个 $v$ 的 ID 到 v_ports 列表。
由于我们保证了 $\sum_{u \in U} d_u = \sum_{v \in V} d_v$ ，所以 u_ports 和 v_ports 列表的长度是相等的（都等于总边数）。
最后，将这两个列表中的端口一一配对。即，对于所有 $i$ ，连接 u_ports[i] 和 v_ports[i]。这样就构造出了所有需要的边。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <queue>

using namespace std;

struct Node {
    int id;
    int degree;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<Node> nodes(n);
    long long total_degree = 0;
    for (int i = 0; i < n; ++i) {
        nodes[i].id = i + 1;
        cin >> nodes[i].degree;
        total_degree += nodes[i].degree;
    }

    if (total_degree % 2 != 0) {
        cout << -1 << endl;
        return 0;
    }

    long long target = total_degree / 2;
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    dp[0][0] = true;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= target; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= nodes[i - 1].degree) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - nodes[i - 1].degree];
            }
        }
    }

    if (!dp[n][target]) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> u_ports, v_ports;
    long long current_sum = target;
    for (int i = n; i >= 1; --i) {
        if (current_sum >= nodes[i - 1].degree && dp[i - 1][current_sum - nodes[i - 1].degree]) {
            for (int k = 0; k < nodes[i - 1].degree; ++k) u_ports.push_back(nodes[i - 1].id);
            current_sum -= nodes[i - 1].degree;
        } else {
            for (int k = 0; k < nodes[i - 1].degree; ++k) v_ports.push_back(nodes[i - 1].id);
        }
    }

    cout << u_ports.size() << endl;
    for (size_t i = 0; i < u_ports.size(); ++i) {
        cout << u_ports[i] << " " << v_ports[i] << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[][] nodes = new int[n][2]; // {id, degree}
        long totalDegree = 0;
        for (int i = 0; i < n; i++) {
            nodes[i][0] = i + 1;
            nodes[i][1] = sc.nextInt();
            totalDegree += nodes[i][1];
        }

        if (totalDegree % 2 != 0) {
            System.out.println(-1);
            return;
        }

        long target = totalDegree / 2;
        boolean[][] dp = new boolean[n + 1][(int) target + 1];
        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nodes[i - 1][1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nodes[i - 1][1]];
                }
            }
        }

        if (!dp[n][(int) target]) {
            System.out.println(-1);
            return;
        }

        List<Integer> uPorts = new ArrayList<>();
        List<Integer> vPorts = new ArrayList<>();
        
        long currentSum = target;
        for (int i = n; i >= 1; i--) {
            if (currentSum >= nodes[i - 1][1] && dp[i - 1][(int) (currentSum - nodes[i - 1][1])]) {
                for (int k = 0; k < nodes[i-1][1]; k++) uPorts.add(nodes[i-1][0]);
                currentSum -= nodes[i - 1][1];
            } else {
                for (int k = 0; k < nodes[i-1][1]; k++) vPorts.add(nodes[i-1][0]);
            }
        }

        System.out.println(uPorts.size());
        for (int i = 0; i < uPorts.size(); i++) {
            System.out.println(uPorts.get(i) + " " + vPorts.get(i));
        }
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return
        n = int(n_str)
        degrees = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    nodes = []
    total_degree = 0
    for i in range(n):
        nodes.append({'id': i + 1, 'degree': degrees[i]})
        total_degree += degrees[i]

    if total_degree % 2 != 0:
        print(-1)
        return

    target = total_degree // 2
    dp = [[False] * (int(target) + 1) for _ in range(n + 1)]
    dp[0][0] = True

    for i in range(1, n + 1):
        degree = nodes[i - 1]['degree']
        for j in range(int(target) + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= degree:
                dp[i][j] = dp[i][j] or dp[i - 1][j - degree]

    if not dp[n][int(target)]:
        print(-1)
        return
    
    u_ports, v_ports = [], []
    current_sum = target
    for i in range(n, 0, -1):
        degree = nodes[i - 1]['degree']
        if current_sum >= degree and dp[i - 1][int(current_sum - degree)]:
            u_ports.extend([nodes[i - 1]['id']] * degree)
            current_sum -= degree
        else:
            v_ports.extend([nodes[i - 1]['id']] * degree)

    print(len(u_ports))
    for i in range(len(u_ports)):
        print(u_ports[i], v_ports[i])

solve()

算法及复杂度

算法: 子集和动态规划 + 端口匹配构造
时间复杂度:
- 子集和 DP 部分： $O(N \cdot T)$ ，其中 $T$ 是目标和，即总度数和的一半。由于 $N \le 100$ 且 $d_i < N$ , $T < 100 \cdot 100 / 2 = 5000$ 。所以这部分复杂度约为 $O(100 \cdot 5000) = O(5 \cdot 10^5)$ 。
- 构造部分：创建端口列表需要 $O(\sum d_i) = O(N^2)$ 。配对需要 $O(T)$ 。
- 总时间复杂度由 DP 部分主导，在给定数据范围内是完全可行的。
空间复杂度:
- DP 表需要 $O(N \cdot T)$ 的空间，约为 $O(100 \cdot 5000)$ 。
- 端口列表需要 $O(T)$ 的空间。
- 总空间复杂度由 DP 表主导。