热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

牛客网小叶的日常巡查与维护

在牛客网的小叶日常巡查与维护工作中,遇到一道关于图论的问题:给定一个无向图,需要求解图中任意两点间的最大路径长度。解决方法是首先选取任意节点P作为起点进行深度优先搜索(DFS),找到距离P最远的节点Q,再以Q为新的起点重复上述过程,最终得到的最大值即为所求的最大路径长度。这种方法有效地避免了对所有节点两两组合的暴力求解,提高了算法效率。

输入:

5
1 2 2
1 3 1
2 4 5
2 5 4

输出:

135

此题求图中两点之间的最长路径,我们可以从任意一点p开始dfs找到一点q,使得pq最长,然后以q为端

点,开始重复上一步的操作,求得最长路径sum,得路费ans=10*sum+(1+sum)*sum/2;

证明:假设最长路径为s--t,第一次dfs得到p-q;

(1)

 

如果pq与st相交于x,因为px+xq>px+(st或者xt),sx+xt>sx+(xq或者xp),所以矛盾,所以q为最长路径的一个端点(s或者t)。

(2)

如果pq与st不相交,那么在st上任取一点x,显然pq>px+xt,可得pq+px>xt,又可得pq+px+xs=sq>xt+xs=st,与假设矛盾。

所以可得从任意一点dfs得到图中最长直径的一个端点。

代码如下:

 1 #include 
 2 #include 
 3 #include 
 4 #include <string.h>
 5 #include 
 6 #include 
 7 #include 
 8 using namespace std;
 9 #define N 74444
10 typedef long long ll;
11 vectorint,ll> >g[N];
12 int lie;
13 ll sum[N],S;
14 void dfs(int fa,int now)
15 {
16     int len=g[now].size();
17     pair<int,long long>p;
18     for(int i=0;i)
19     {
20         p=g[now][i];
21         if(p.first!=fa)
22         {
23            sum[p.first]=sum[now]+p.second;
24            if(S<sum[p.first]){
25             lie=p.first;
26             S=sum[p.first];
27            }
28            dfs(now,p.first);
29         }
30     }
31 }
32 int main()
33 {
34     int n;
35     scanf("%d",&n);
36     for(int i=1;i)
37     {
38         int x,y;
39         long long v;
40         scanf("%d%d%lld",&x,&y,&v);
41         g[x].push_back(make_pair(y,v));
42         g[y].push_back(make_pair(x,v));
43     }
44     S=0;
45     dfs(0,1);
46     S=0;
47     memset(sum,0,sizeof(sum));
48     dfs(0,lie);
49     printf("%lld\n",S*10+(1+S)*S/2);
50     return 0;
51 }

 


推荐阅读
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 本文探讨了如何优化和正确配置Kafka Streams应用程序以确保准确的状态存储查询。通过调整配置参数和代码逻辑,可以有效解决数据不一致的问题。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
author-avatar
Just忽略我_559
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有