在C ++中最大化树的任意两个顶点之间的度的乘积之和
给定任务是构造一个具有给定整数N的树，使得所有有序对(x,y)的度(x)*度(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()函数初始化intsum=0并创建具有条件x<N和y<N的初始化x=1和y=1的嵌套循环。
在嵌套循环内，首先检查if（x==y），如果是，则添加continue；声明
否则，初始化intdegree=2并使用if语句检查if（x==1||x==n）。如果是这样，则将degreeX=1。然后初始化intdegree=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;
//节点x的初始化程度为2-
int degreeX = 2;
//如果x是叶节点或根节点
if (x == 1 || x == N)
degreeX = 1;
//节点y的初始化度为2-
int degreeY = 2;
//如果y是叶节点或根节点
if (y == 1 || y == N)
degreeY = 1;
//更新总和
sum += (degreeX * degreeY);
}
}
return sum;
}
//主要功能
int main(){
int N = 5;
cout << Max(N);
}输出结果
如果运行上面的代码，我们将获得以下输出-
50