C ++中树中两个不相交的路径的最大乘积
在本教程中，我们将讨论一个程序，以查找树中两个不相交的路径的最大乘积。
为此，我们将提供一个具有n个节点的无向树。我们的任务是在树中找到两条路径，以使它们的乘积最大且不相交。
示例
#include <bits/stdc++.h>
using namespace std;
//返回最大长度路径
int dfs(vector<int> g[], int& curMax, int u, int v) {
int max1 = 0, max2 = 0, total = 0;
for (int i = 0; i < g[u].size(); i++) {
if (g[u][i] == v)
continue;
total = max(total, dfs(g, curMax, g[u][i], u));
if (curMax > max1) {
max2 = max1;
max1 = curMax;
}
else
max2 = max(max2, curMax);
}
total = max(total, max1 + max2);
curMax = max1 + 1;
return total;
}
//返回非相交路径的乘积
int maxProductOfTwoPaths(vector<int> g[], int N) {
int res = INT_MIN;
int path1, path2;
for (int i = 0; i < N; i++) {
for (int j = 0; j < g[i].size(); j++) {
int curMax = 0;
path1 = dfs(g, curMax, g[i][j], i);
curMax = 0;
path2 = dfs(g, curMax, i, g[i][j]);
res = max(res, path1 * path2);
}
}
return res;
}
void addEdge(vector<int> g[], int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
}
int main() {
int edges[][2] = {{1, 8}, {2, 6}, {3, 1},{5, 3}, {7, 8}, {8, 4},{8, 6} };
int N = sizeof(edges)/sizeof(edges[0]);
vector<int> g[N + 2];
for (int i = 0; i < N; i++)
addEdge(g, edges[i][0], edges[i][1]);
cout << maxProductOfTwoPaths(g, N) << endl;
return 0;
}输出结果
6