题解 | 小红的二分图构造

while True:
    try:
        n = int(input())    # 节点数量
        d = [0] + list(map(int, input().split()))   # 节点度数
        total = sum(d)
        if total % 2 == 1:      # 节点度数之和必须是偶数
            print(-1)
        else:   # 把节点分成2个集合，集合的度数相等即可。
            # 转化成01背包问题
            dp = [[-float('inf')] * (total // 2 + 1) for _ in range(n + 1)]
            # -float('inf') 表示负无穷，在某些算法中，可以表示某个状态是不可达的或无效的
            # dp[i][j] 表示前i个点，A集合的度数和为j时，A集合中的节点个数
            # 构造dp数组的时候，不能初始化为0，不然会影响最终结果
            dp[0][0] = 0
            for i in range(1, n + 1):
                for j in range(total // 2 + 1):
                    dp[i][j] = dp[i - 1][j]     # 不选当前节点
                    if j >= d[i]:
                        dp[i][j] = max(dp[i][j], dp[i-1][j-d[i]] + 1)   # 选当前节点
                        # 如果初始化为0，当i=1，j > d[i]时，dp[i][j]的值为1
                        # 很显然这不成立，此时无法构成A集合，dp[i][j]的值应该是无效值

            if dp[n][total // 2] <= 0:
                print(-1)
            else:   # 分组
                ni, nj = n, total // 2
                v1, v2 = [], []
                while ni > 0:
                    if dp[ni][nj] == dp[ni - 1][nj]:    # 没选i，分到2组
                        v2.append(ni)
                        ni -= 1
                    else:       # 选i，分到1组
                        v1.append(ni)
                        nj -= d[ni]
                        ni -= 1
                res = []
                while v1 and v2:
                    res.append([v1[0], v2[0]])
                    d[v1[0]] -= 1
                    d[v2[0]] -= 1
                    if d[v1[0]] == 0:
                        v1.pop(0)
                    if d[v2[0]] == 0:
                        v2.pop(0)
                print(total // 2)
                for x, y in res:
                    print(x, y)
    except:
        break