首页 > 试题广场 >

小红的二分图构造

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

热度指数：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

说明

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

算法知识视频讲解

Java

Sen🍓🍀

import java.util.*;

// @@@ 二分图：节点划分两部分，两部分的度相等 → 01背包 装满sum/2
//     要知道具体的分配方案，由dp[n][v]反推
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] d = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            d[i] = in.nextInt();
            sum += d[i];
        }
        if (sum % 2 != 0) { // 度数和应该为偶数 → -1
            System.out.println(-1);
            return;
        }

        int v = sum / 2;
        int[][] dp = new int[n + 1][v + 1]; // 01背包
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                if (j >= d[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - d[i - 1]] + d[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        if (dp[n][v] != v) { // 没装满 → -1
            System.out.println(-1);
            return;
        }

        Set<Integer> set = new HashSet<>();
        for (int i = n, j = v; i > 0 && j > 0; ) { // 反推所选方案
            if (dp[i][j] == dp[i - 1][j]) { // 不选节点i
                i--;
            } else { // 选节点i
                set.add(i - 1);
                j -= d[i - 1];
                i--;
            }
        }
        List<Integer> list1 = new ArrayList<>(set);
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < n; i++) if (!set.contains(i)) list2.add(i);
        // System.out.println(list1.size() + " " + list2.size() + " " + v);

        StringBuilder sb = new StringBuilder();
        sb.append(v).append('\n');
        for (int i = 0, j = 0; i < list1.size() && j < list2.size();) {
            while (d[list1.get(i)] > 0 && d[list2.get(j)] > 0) {
                sb.append(list1.get(i) + 1).append(' ').append(list2.get(j) + 1).append('\n');
                d[list1.get(i)]--;
                d[list2.get(j)]--;
            }
            if (d[list1.get(i)] == 0) i++;
            if (d[list2.get(j)] == 0) j++;
        }
        System.out.println(sb.toString());
    }
}

发表于 2025-05-30 10:09:23 回复(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)

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)

Java

牛客430757235号

//EASY 弄懂思路很简单

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

int n = in.nextInt();

int data[] = new int[n];

int total = 0;

for (int i = 0; i < n; i++) {

data[i] = in.nextInt();

total = total + data[i];

}

if (total % 2 != 0) {

System.out.println(-1);

return;

}

int target = total / 2;

boolean[] pan = new boolean[target + 1];

pan[0] = true;

int[] prev = new int[target + 1];

Arrays.fill(prev, -1);

for (int i = 0; i < n; i++) {

int di = data[i];

for (int s = target; s >= di; s--) {

if (!pan[s] && pan[s - di]) {

pan[s] = true;

prev[s] = i;

}

if(prev[target]==-1){

System.out.println(-1);

return;

}

boolean[] dingwei = new boolean[n];

int curr = target;

while(curr>0&&prev[curr]!=-1){

int i = prev[curr];

if(dingwei[i])break;

dingwei[i]=true;

curr = curr-data[i];

}

List<Integer> U = new ArrayList<>();

List<Integer> V = new ArrayList<>();

for(int i = 0;i<n;i++){

if(dingwei[i]){

U.add(i);

}else{

V.add(i);

}

}//U放的是true的 V放false的

if(U.isEmpty()||V.isEmpty()){

System.out.println(-1);

return;

}

Queue<int[]> Uheap = new PriorityQueue<>((o1, o2) -> o2[0]-o1[0]);

Queue<int[]> Vheap = new PriorityQueue<>((o1, o2) -> o2[0]-o1[0]);

for(int i:U){

Uheap.add(new int[]{data[i],i+1});

}

for(int i:V){

Vheap.add(new int[]{data[i],i+1});

}

//已经将U V集合分开了接下来该用贪心算法进行配边输出了

List<String> result = new ArrayList<>();

while(!Uheap.isEmpty()&&!Vheap.isEmpty()){//终止条件

int[] x = Uheap.poll();

int[] y = Vheap.poll();

int num = Math.min(x[0],y[0]);

for(int i = 0;i<num;i++){

result.add(x[1]+" "+y[1]);

}

x[0] = x[0] - num;

y[0] = y[0] - num;

if(x[0]>0)Uheap.add(x);

if(y[0]>0)Vheap.add(y);

}

System.out.println(result.size());

for(String resul:result){

System.out.println(resul);

}

发表于 2025-04-04 14:39:07 回复(0)

提交观点

问题信息

动态规划

难度：

5条回答 94收藏 266浏览

小红的二分图构造

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题