在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()函数初始化int sum = 0并创建具有条件x <N和y <N的初始化x = 1和y = 1的嵌套循环。

• 在嵌套循环内，首先检查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;
         //节点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