tiyi:给你n个节点和n-1条边(无环),求在这个图中找到 两条路径,两路径不相交,求能找的两条路径的长度的乘积最大值

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
const int mod=100000000;
ll max(ll a,ll b)
{return a>b?a:b;};
int min(int a,int b)
{return a<b?a:b;}; struct Edge{
int u,v;
}e[205]; vector<int> G[205];
int vis[205],step[205],s,len; int bfs(int a,int pre)
{
int s=a;
len=0;
MM(vis,0);
MM(step,0);
queue<int> q;
q.push(a);
vis[pre]=vis[a]=1;
while(q.size())
{
int u=q.front();q.pop();
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(vis[v]) continue;
q.push(v);
vis[v]=1;
step[v]=max(step[v],step[u]+1);
if(step[v]>len)
{
len=step[v];
s=v;
}
}
}
return s;
}//求树的直径len模板
int main()
{
int n,u,v;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<n;i++)
{
scanf("%d %d",&e[i].u,&e[i].v);
G[e[i].u].push_back(e[i].v);
G[e[i].v].push_back(e[i].u);
} int ans=0;
for(int i=1;i<n;i++)
{
int u=e[i].u,v=e[i].v;
bfs(bfs(u,v),v);
int x=len;
bfs(bfs(v,u),u);
x*=len;
ans=max(ans,x);
}
printf("%d\n",ans);
}
return 0;
}

  分析:枚举每条边,将图拆成两棵树(保证没有交点),分别求得两棵树的直径,乘积就是此时的最大值

树的直径资料:链接

最新文章

  1. html插入链接
  2. JAVA JDBC连接 SQLServer2012
  3. Silverlight DataGrid标题行居中
  4. C# for AUTOCAD ActiveX获取图形对象坐标程序
  5. ReactEurope Conf 参会感想
  6. sql 减去分钟
  7. 浅谈 zookeeper 原理,安装和配置
  8. FDG内存分配器笔记
  9. MongoDB3.4 shell CRUD操作
  10. kali&amp;BT安装好之后无法上网或者无法获得内网IP
  11. 小白也能看懂插件化DroidPlugin原理(一)-- 动态代理
  12. Docker问题: Layer already being pulled by another client. Waiting.什么原因
  13. 获取具有指定扩展数据的所有实体的Id,并存入Id数组中
  14. 百度语音+react+loopback实现语音合成返回播放
  15. Java Web 浏览器关闭后Session就会被销毁吗?
  16. Hibernate的入门(概念1):
  17. 资源中心的ES 服务的COM.IFLYTEK.ERSP.API.RESOURCEAPI 接口注册ZOOKEEPER失败,解决记录
  18. Recurrent NN vs Recursive NN
  19. Linux多进程和多线程的一次gdb调试实例
  20. 【性能测试】:操作NMON的shell脚本

热门文章

  1. asp.net之后台使用根目录运算符
  2. POJ - 1815 Friendship (最小点割集)
  3. WPF中Brush类型
  4. vue--微信支付
  5. 多Y轴示例
  6. LLVM源码安装教程
  7. vue项目打包后在IE浏览器报错,页面显示空白
  8. mysql 5.7.24 root密码重置
  9. 00常见的Linux系统版本
  10. Zabbix Agent配置文件详解