数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律使用 C++ 计算树中两个不相交路径的最大乘积
在此问题中，我们提供一个具有 n 个节点的无根连通树 T。我们的任务是编写一个程序，使用 C++ 查找树中两个不相交路径的最大乘积。
问题说明 − 找到树中两个不相交路径的最大乘积。我们将找到所有不相交的路径，然后再计算其长度乘积。
我们举个例子来说明这个问题，
输入
图形 −
输出
8
说明
考虑的不相交路径是 C-A-B 和 F-E-D-G-H。
长度为 2 和 4。乘积 = 8。
解决方案
这个问题的解决方案是使用 DFS 遍历树。找到移除连接边之后仍然唯一的路径。然后，在路径上进行迭代并找到其长度。然后，我们将两条路径配对并计算其长度的乘积。两者被考虑的方式是使它们的乘积变为最大。
实现我们解决方案的程序，
范例
#include <bits/stdc++.h>
using namespace std;
int TreeTraverse(vector<int> graph[], int& currPathMax, int val1, int val2){
int max1 = 0, max2 = 0, maxVal = 0;
for (int i = 0; i < graph[val1].size(); i++) {
if (graph[val1][i] == val2)
continue;
maxVal = max(maxVal, TreeTraverse(graph, currPathMax,
graph[val1][i], val1));
if (currPathMax > max1) {
max2 = max1;
max1 = currPathMax;
}
else
max2 = max(max2, currPathMax);
}
maxVal = max(maxVal, max1 + max2);
currPathMax = max1 + 1;
return maxVal;
}
int FindMaxProductPath(vector<int> graph[], int Size) {
int maxProd = -10;
int pathA, pathB;
int currPathMax, prod;
for (int i = 0; i < Size; i++) {
for (int j = 0; j < graph[i].size(); j++){
currPathMax = 0;
pathA = TreeTraverse(graph, currPathMax, graph[i][j],i);
currPathMax = 0;
pathB = TreeTraverse(graph, currPathMax, i,graph[i][j]);
prod = (pathA * pathB);
maxProd = max(maxProd, prod);
}
}
return maxProd;
}
void insertEdge(vector<int> graph[], int val1, int val2){
graph[val1].push_back(val2);
graph[val2].push_back(val1);
}
int main(){
int Size = 8;
vector<int> graph[Size + 2];
insertEdge(graph, 1, 2);
insertEdge(graph, 2, 4);
insertEdge(graph, 3, 1);
insertEdge(graph, 5, 4);
insertEdge(graph, 7, 8);
insertEdge(graph, 8, 4);
insertEdge(graph, 5, 6);
cout<<"Maximum product of two non-intersecting paths of tree is "<<FindMaxProductPath(graph, Size)<<"\n";
return 0;
}输出
Maximum product of two non-intersecting paths of tree is 8
更新于:2020 年 9 月 15 日
107 次浏览
广告