题意,移动一条边,使得树的直径最小。
首先枚举拆掉的边, 拆掉边后,原图变成2颗树,然后重新连接两颗子树的某两个结点, 那么,此时答案(新树的直径)只有可能有3种情况。
1、直径完全在1子树中。
2、直径完全在2子树中。
3、直径经过了 重新建立的那条边,也就是贯穿了2颗子树。
用这3种的最大值更新ans。
求树的直径的方法可以通过dfs或者bfs,O(n)时间求出。
现在的问题在于,如何求第3种。
假设1子树存在一个点,这个点满足,任意一个点到它的距离的最大值最小。同样,2子树也找到这样一个点,然后连接这2个点,这样求得的最长链一定是最短的。
问题转化为,如何求树上的一个点,使得任意一个点到它的距离的最大值最小
假设这样一个点a不在直径上,那么它到最远距离的点,一定会和直径产生一个交点b(由直径的性质),那么a到其他点(设为x)的最大距离一定大于b到其他点(直径的端点,设为y)的最大距离。所以a一定在直径上。
证明:其实x点就是直径的端点,因为,若x不是直径的端点,那么就有ax>ay ==>bx>by==>那么y就不应该是直径的端点了。而是x。所以x一定是直径的端点。。所以ax=ab+bx,所以ax>bx。
实际上还有一个优化,就是枚举边的时候,不必枚举每一条边,只需要枚举原图的直径上的边就可以了,因为只有删掉原图的直径边,才能使直径变短。这个优化可以把时间从4800+ms降到90+ms。
题解:枚举原图直径上的边,分别求出拆掉这条边后,1,2两颗子树的直径l1,l2,再利用上述的证明求出l3
ans = min(ans,max(l1,l2,l3));复杂度为O(n^2)
我把题目中的dfs都用一个函数写下来了,所以主函数看上去比较冗长。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> tree[2600];
int maps[2600][2600];
int dp[2600];
int fat[2600];
int FA[2600];
int maxn,node,ans;
void input()
{
int a,b,c;
scanf("%d",&n);
for(int i=0;i<=n;i++)
{
tree[i].clear();
}
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
tree[a].push_back(b);
tree[b].push_back(a);
maps[a][b]=maps[b][a]=c;
}
}
void dfs(int now,int NOT,int fa,int num=0)
{
if(fa==-1) node=now;
for(int i=0;i<tree[now].size();i++)
{
int to=tree[now][i];
if(to!=fa&&to!=NOT)
{
fat[to]=now;
dp[to]=dp[now]+maps[now][to];
dfs(to,NOT,now);
}
}
if(dp[now]>maxn)
{
maxn=dp[now];
node=now;
}
}
int main()
{
int cas,a,b,c;
cin>>cas;
int ca=1;
while(cas--)
{
input();
ans=0x3f3f3f3f;
dfs(0,-1,-1);
int aa=node;
dfs(aa,-1,-1);
int bb=node;
for(int i=0;i<n;i++) FA[i]=fat[i];
while(bb!=aa)
{
int i=bb;
int l1,l2;
int t1=0x3f3f3f3f,t2=0x3f3f3f3f;
maxn=0;dp[i]=0;dfs(i,FA[bb],-1);int a=node;
maxn=0;dp[a]=0;dfs(a,FA[bb],-1);int b=node;
l1=maxn;
if(a==b)
{
l1=0;
t1=0;
}
else
{
while(b!=a)
{
t1=min(t1,max(dp[b],maxn-dp[b]));
b=fat[b];
}
}
maxn=0;dp[FA[bb]]=0;dfs(FA[bb],i,-1);a=node;
maxn=0;dp[a]=0;dfs(a,i,-1);b=node;
l2=maxn;
if(a==b)
{
l2=0;
t2=0;
}
else
{
while(b!=a)
{
t2=min(t2,max(dp[b],maxn-dp[b]));
b=fat[b];
}
}
ans=min( ans, max(max(l1,l2),t1+t2+maps[i][FA[bb]]) );
bb=FA[bb];
}
printf("Case %d: %d\n",ca++,ans);
}
return 0;
}
分享到:
相关推荐
智能制造的数字化工厂规划qytp.pptx
罗兰贝格:德隆人力资源管理体系gltp.pptx
JAVA3D的网络三维技术的设计与实现
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
基于J2EE的B2C电子商务系统开发
麦肯锡_xx保险员工培训咨询报告gltp.pptx
JAVA社区网络服务系统
备自投tp.pptx
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
JSP高校教务排课管理系统,管理员角色包含以下功能:课程申请管理,课程设置管理,课程情况查看,专业设置查看,排课管理,系办人员管理,教师管理,学生管理,教室管理,班级管理,管理员登录等功能。教师角色包含以下功能:教师角色登录,申请增加课程,学生管理,成绩录入管理,课程安排管理等功能。学生角色包含以下功能:学生角色登录,基本信息查看,选课功能安排,课程表查看,成绩查询等功能。 本项目实现的最终作用是基于JSP高校教务排课管理系统 分为3个角色 第1个角色为管理员角色,实现了如下功能: - 专业设置查看 - 学生管理 - 排课管理 - 教室管理 - 教师管理 - 班级管理 - 管理员登录 - 系办人员管理 - 课程情况查看 - 课程申请管理 - 课程设置管理 第2个角色为教师角色,实现了如下功能: - 学生管理 - 成绩录入管理 - 教师角色登录 - 申请增加课程 - 课程安排管理 第3个角色为学生角色,实现了如下功能: - 基本信息查看 - 学生角色登录 - 成绩查询 - 课程表查看 - 选课功能安排
第21章spring-mvc之缓存
华为网盘高级版
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Java聊天室程序(java)
产品线经理转身赋能zzn.pptx
JAVA泡泡堂网络游戏的设计与实现
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
基于python深度度量学习准确预测蛋白质二级结构源码(期末大作业).zip已获导师指导并通过的97分的高分大作业设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。 基于python深度度量学习准确预测蛋白质二级结构源码(期末大作业).zip已获导师指导并通过的97分的高分大作业设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。 基于python深度度量学习准确预测蛋白质二级结构源码(期末大作业).zip已获导师指导并通过的97分的高分大作业设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。 基于python深度度量学习准确预测蛋白质二级结构源码(期末大作业).zip已获导师指导并通过的97分的高分大作业设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。 基于python深度度量学习准确预测蛋白质二级结构源码(期末大作业).zip已获导师指导并通过的97分的高分大作业设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目完整确保可以运行。
python: 【0514】基于Python省市区三级地址库.zip
该包包括6个完全装配和纹理的3D公民角色,以2种颜色变化的男性和女性角色为特色,45个带有卡通着色器的风格化道具。 完全装配+搅拌机形状 MIXAMO兼容 这些卡通风格的人形公民角色设计得非常吸引人和引人注目,非常适合用于游戏、动画和其他数字项目。 通过各种各样的姿势和表情,你可以很容易地与这些角色一起创造出观众一定会喜欢的动态场景。