首页 > 试题广场 >

小红的二分图构造

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

热度指数：2021 时间限制：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)

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)

提交观点

问题信息

动态规划

难度：

2条回答 95收藏 277浏览

小红的二分图构造

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题