小红希望你构造一个二分图，满足第 个节点的度数恰好等于 。你能帮帮她吗？ 二分图是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 与 ，使得图中的每一条边都连接 中的一个节点与 中的一个节点。
区块链毕设网qklbishe.com为您提供问题的解答
小红希望你构造一个二分图，满足第
个节点的度数恰好等于
。你能帮帮她吗？
二分图是一张满足如下条件的图：它的节点可以被分成两个不相交的集合
与
，使得图中的每一条边都连接
中的一个节点与
中的一个节点。
//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);
}
}
}
39:07
以上就是关于问题小红希望你构造一个二分图，满足第 个节点的度数恰好等于 。你能帮帮她吗？
二分图是一张满足如下条件的图：它的节点可以被分成两个不相交的集合 与 ，使得图中的每一条边都连接 中的一个节点与 中的一个节点。的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}