首页 > 试题广场 >

小红的二分图构造

[编程题]小红的二分图构造
  • 热度指数：308 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红希望你构造一个二分图，满足第 i 个节点的度数恰好等于 d_i 。你能帮帮她吗？

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

输入描述:
\hspace{15pt}第一行输入一个正整数 n \left(1\leq n \leq 100\right) ，代表二分图的节点数量。
\hspace{15pt}第二行输入 n 个正整数 d_1, d_2, \cdots, d_n \left(1\leq d_i \leq n-1\right) ，代表每个节点的度数。


输出描述:
\hspace{15pt}如果答案不存在，直接输出 -1 。

\hspace{15pt}否则，请参考下方的格式输出。
\hspace{15pt}第一行输出一个整数 m 代表边的数量。
\hspace{15pt}接下来的 m 行，每行输出两个正整数 u,v \left(1\leq u,v \leq n\right) 代表节点 u 和节点 v 有一条边连接。
\hspace{15pt}构造的图可以包含重边，但不能包含自环。构造的最终的图可以不连通，你只需要保证每个连通分量均为二分图。

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

输入

3
1 2 1

输出

2
1 2
2 3

说明

\hspace{15pt}构造的图是一棵树，显然所有树都是二分图。
示例2

输入

3
2 2 2

输出

-1

说明

\hspace{15pt}只能构造一个三元环，显然不是二分图。
算法知识视频讲解
添加回答
Java
牛客430757235号头像 牛客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)
提交观点

问题信息

难度：
1条回答 4浏览

热门推荐

相关试题

小红的二分图构造

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号