问题概述：已知图中有n个点，这n个点由n-1条路完全连通，请找出图中最长的且不相交的两条路径并求其乘积
输入样例： 对应输出：
6 8
1 2
2 3
2 4
5 4
6 4
思路：枚举各个边将该边删除，然后分别找出分开两部分的最长的一条路径，求乘积即可，最后找个最大值
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int> a[205]; int s; int Sech(int v, int x); int main() { int x, y, i, j, n, max; scanf("%d", &n); max = 0; for(i=1;i<=n-1;i++) { scanf("%d%d", &x, &y); a[x].push_back(y); a[y].push_back(x); } for(i=1;i<=n;i++) { for(j=0;j<=a[i].size()-1;j++) { s = 0; x = Sech(i, a[i][j]); y = Sech(a[i][j], i); /*传入两个点(准备删除连接这两个点的路并计算)*/ if(x*y>max) /*当然每对点都会被传入两次,略微费时*/ max = x*y; /*求出最大乘积*/ } } printf("%d\n", max); return 0; } int Sech(int v, int x) /*对于每次搜索,需要求出①:这个点最长枝的长度②:这个点最长的枝与次长的枝之和*/ { /*搜索递推关系:③这个点最长枝的长度+1等于上一个节点的其中一条枝的长度*/ int i, max1, max2, sum; /*搜索目的:④求出②的最大值*/ max1 = max2 = sum = 0; for(i=0;i<=a[v].size()-1;i++) { if(a[v][i]==x) continue; sum = max(sum, Sech(a[v][i], v)); /*④*/ if(s>max1) /*①*/ { max2 = max1; max1 = s; } else max2 = max(max2, s); } sum = max(max1+max2, sum); /*②*/ s = max1+1; /*③*/ return sum; }
