数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在 C++ 中最大化树中任意两个顶点之间度数乘积之和
给定任务是用给定的整数 N 构造一棵树，使得所有有序对 (x,y) 的 degree(x) * degree(y) 之和最大，且 x 不等于 y。
输入 −N=5
输出 −50
解释
1 \ 2 \ 3 \ 4 \ 5 Degree of 1st node = 1 Degree of 2nd node = 2 Degree of 3rd node = 2 Degree of 4th node = 2 Degree of 5th node = 1
所有有序对 (x, y) 的所有度数的乘积 −
1st node = 1*2 + 1*2 + 1*2 + 1*1 = 7 2nd node = 2*1 + 2*2 + 2*2 + 2*1 = 12 3rd node = 2*1 + 2*2 + 2*2 + 2*1 = 12 4th node = 2*1 + 2*2 + 2*2 + 2*1 = 12 5th node = 1*2 + 1*2 + 1*2 + 1*1 = 7 Total sum = 50
输入 −N=7
输出 −122
下面程序中使用的算法如下
树中所有节点的度数之和为 − (2 * N) – 2。这里 N=树中节点数。为了最大化总和，必须最小化叶节点数。
在 Max() 函数内，初始化 int sum=0 并创建嵌套循环，初始化 x=1 和 y=1，条件为 x<N 和 y<N。
在嵌套循环内，首先检查 if(x==y)，如果是，则添加 continue; 语句
否则，初始化 int degree=2，并使用 if 语句检查 if(x==1 || x==n)。如果是，则将 degreeX=1。然后初始化 int degree=2，对变量 y 执行相同的操作
最后，在关闭循环之前，通过编写 sum = (degreeX + degreeY) 来更新 sum 变量
示例
#include <bits/stdc++.h>
using namespace std;
int Max(int N){
int sum = 0;
for (int x = 1; x <= N; x++){
for (int y = 1; y <= N; y++){
if (x == y)
continue;
//Initializing degree for node x to 2
int degreeX = 2;
//If x is the leaf node or the root node
if (x == 1 || x == N)
degreeX = 1;
//Initializing degree for node y to 2
int degreeY = 2;
//If y is the leaf node or the root node
if (y == 1 || y == N)
degreeY = 1;
//Updating sum
sum += (degreeX * degreeY);
}
}
return sum;
}
//Main function
int main(){
int N = 5;
cout << Max(N);
}输出
如果我们运行上述代码，我们将得到以下输出：
50
更新于：2020年8月17日
254 次浏览
广告