首页 > 试题广场 >

小红的二分图构造

[编程题]小红的二分图构造

热度指数：2003 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红希望你构造一个二分图，满足第 $i$ 个节点的度数恰好等于 $d_i$ 。你能帮帮她吗？

$\hspace{15pt}$ 二分图是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 $U$ 与 $V$ ，使得图中的每一条边都连接 $U$ 中的一个节点与 $V$ 中的一个节点。

输入描述:

第一行输入一个正整数  ，代表二分图的节点数量。
第二行输入  个正整数  ，代表每个节点的度数。

输出描述:

如果答案不存在，直接输出  。

否则，请参考下方的格式输出。
第一行输出一个整数  代表边的数量。
接下来的  行，每行输出两个正整数  代表节点  和节点  有一条边连接。
构造的图可以包含重边，但不能包含自环。构造的最终的图可以不连通，你只需要保证每个连通分量均为二分图。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

3
1 2 1

输出

2
1 2
2 3

说明

构造的图是一棵树，显然所有树都是二分图。

示例2

输入

3
2 2 2

输出

-1

说明

只能构造一个三元环，显然不是二分图。

算法知识视频讲解

Python 3

dthcle_

只能想到暴力解法了 。。。。

n = int(input())

d = list(map(int, input().split()))
nodes = []
for idx, node in enumerate(d):
    nodes.append((idx, node))  # (node名称, 度数)

total_sides = sum(d)
if total_sides % 2 != 0:
    print(-1)
    exit(0)
target_sides = int(total_sides // 2)

# 二分图的性质
# 1. 左右两边度相等
# 2. 左边度的最大值不能超过右边节点数量，右边同理。因为允许重边，所以不需要进一步考虑节点和边的对应关系
sorted_nodes = sorted(nodes, key=lambda x: x[1], reverse=True)

# 先想办法让左右两边度相等
curr_side = 0
def dfs(curr_side, target_side, begin, n):
    if curr_side == target_side:
        return []
    if begin == n-1:
        return None
    for i in range(begin+1, n):
        curr_node = sorted_nodes[i]
        choices = dfs(curr_side+curr_node[1], target_side, i, n)  # 选择当前node
        if choices is not None:
            choices.append(list(curr_node))
            return choices
        choices = dfs(curr_side, target_side, i, n)  # 不选择当前node
        if choices is not None:
            return choices
    return None

left_list = dfs(0, target_sides, -1, n)
if left_list is None:
    print(-1)
    exit(0)
max_sides = left_list[0][1]
if max_sides + len(left_list) > n:
    print(-1)
    exit(0)

left_list = sorted(left_list, key=lambda x: x[0])  # 按序号排序
right_list = []
last_idx = 0
for each in left_list:
    for i in range(last_idx, each[0]):
        right_list.append(list(nodes[i]))
    last_idx = each[0] + 1
for i in range(last_idx, n):
    right_list.append(list(nodes[i]))

# 打印边数量
print(target_sides)
# 从left_list一个一个取值 然后对应到right_list
curr_right_idx = 0
for each in left_list:
    while each[1] > 0:
        tmp_r = right_list[curr_right_idx]
        if tmp_r[1] == 0:
            curr_right_idx += 1
            continue
        tmp_min = min(tmp_r[1], each[1])
        tmp_r[1] -= tmp_min
        each[1] -= tmp_min
        for _ in range(tmp_min):
            print(each[0]+1, tmp_r[0]+1)  # 序号要+1

发表于 2026-01-21 20:56:12 回复(0)

Python 3

呼呼伊阿

n=int(input())

list1=list(map(int,input().split()))

sum1=sum(list1)

if sum1%2!=0:

print(-1)

exit()

choice=[[0]]*(sum1//2+1)

for i,item in enumerate(list1):

for j in range(sum1//2,item-1,-1):

if choice[j-item][0]+item>choice[j][0]:

item1=choice[j-item]+[]

item1[0]+=item

choice[j]=item1+[i+1]

if choice[-1][0]==sum1//2:

left=choice[-1][1:]

left.sort()

right=[]

for m in range(1,n+1):

if m not in left:

for z in range(list1[m-1]):

right.append(m)

else:

for z in range(list1[m-1]-1):

left.append(m)

print(len(left))

for k in range(len(left)):

list2=[left[k],right[k]]

list2.sort()

print(' '.join(map(str,list2)))

else:

print(-1)

发表于 2025-05-22 20:58:05 回复(0)

Python 3

牛客944845056号

import sys

n=int(sys.stdin.readline())

ns=list(map(int,sys.stdin.readline().split()))

total=sum(ns)

if total%2!=0:

print(-1)

exit()

target=total//2

# 动态规划找是否存在度数和为target的节点组合

dp=[False]*(target+1) # dp[i]表示度数和为i的节点组合是否存在

dp[0]=True # 度数和为0的组合肯定存在

road=[[] for _ in range(target+1)] # road[i]记录度数和为i的节点组合的下标

for i in range(len(ns)):

d_i=ns[i]

for cur_sum in range(target,d_i-1,-1):

if not dp[cur_sum] and dp[cur_sum-d_i]: # 若记录路径则not dp[cur_sum]不可省略。

dp[cur_sum]=True

road[cur_sum]=road[cur_sum-d_i]+[i]

if not dp[target]:

print(-1)

exit()

# 把节点分为U、V集合

U=[(ns[idx],idx) for idx in road[target]]

V=[(ns[idx],idx) for idx in range(n) if idx not in road[target]]

# 在U、V集合间创造边

link=[]

while U and V:

u_value,u_idx=U.pop()

v_value,v_idx=V.pop()

k=min(u_value,v_value)

link.append((u_idx+1,v_idx+1,k))

if u_value-k>0:

U.append((u_value-k,u_idx))

if v_value-k>0:

V.append((v_value-k,v_idx))

print(target)

for u,v,k in link:

for _ in range(k):

print(u,v)

发表于 2025-05-19 20:39:55 回复(1)

提交观点

问题信息

动态规划

难度：

3条回答 94收藏 265浏览

小红的二分图构造

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题