首页 > 试题广场 >

小红的二分图构造

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

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

说明

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

算法知识视频讲解

xinglili

发表于 2024-12-22 22:33:05

A~E题 A题先找到>=l的最小x的倍数再判断是否<=r 或者先找到<=r的最大x的倍数再判断是否>=l都可以 void solved() { int l,r,x; cin>>l>>r>>x; int mi=(l+x-1)/x*x; 展开全文

牛客856751393号

发表于 2025-03-07 21:12:06

while True: try: n = int(input()) # 节点数量 d = [0] + list(map(int, input().split())) # 节点度数 total = sum(d) if t 展开全文

Gooby114514

发表于 2024-12-24 14:15:09

E 小红的二分图构造先思考如何把判掉。由于一条边贡献的度，所以所有点的度数和必须为偶数。接下来考虑如何构造。我们可以直接按照二分图的定义来，把原来的所有点分成两个集合，保证两个集合的度数和相等即可。那么现在问题就变成了如何分集合，注意到这是一个经典01背包，但是需要知道具体的方案展开全文

丨阿伟丨

发表于 2025-09-10 13:51:35

题目链接 PEEK154 小红的二分图构造题目描述给定个节点的度数序列 (, )，要求构造一个含个节点的二分图，使得第个节点的度数恰好为。如果无法构造，输出 -1。否则，输出图的边数和所有边。构造的图可以包含重边，但不能有自环。解题思路这是一个构造性问题。解决问题的关键在于展开全文

牛客327038019号

发表于 2025-09-28 23:12:51

#include <iostream> #include <vector> #include<algorithm> using namespace std; struct bo { int xu; int shu; }; bool zhao(bo a,bo b 展开全文

LR我又馋了

发表于 2025-07-23 23:04:08

from math import inf def solved(): n = int(input()) degree = [0] + list(map(int, input().split())) k = sum(degree) if k % 2== 1: 展开全文

TQ988

发表于 2025-07-08 17:31:22

import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scan 展开全文

爱读书的高级磨洋工很野蛮

发表于 2025-08-06 12:57:44

def getHalf(d,s,t): now=0 for i,j in enumerate(s): if j==1: now+=d[i] if now==t//2: return s elif now>t 展开全文

野蛮的小学生在创作

发表于 2025-03-26 19:21:29

import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class hj118 { public static void main(String[] args) { 展开全文

Goldminer

发表于 2025-04-22 15:29:22

#include <iostream> #include <vector> #include <algorithm> using namespace std; void solved() { int n; // 节点数量 cin >> 展开全文

问题信息

动态规划

难度：

5条回答 94收藏 264浏览

小红的二分图构造

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题