poj 1383 Labyrinth (树的直径裸题)

poj 1383题目链接

题意:一个迷宫图,求最远两点的距离是多少,保证每两个点都是联通的。

思路:树的直径。

 

 

hdu 4123 Bob’s Race (树的直径+尺取+rmq)(珍爱生命,远离log)

hdu 4123 题目链接

 

题意:一棵树,定义d[i]为点i到树上某点的最大距离。。。给出若干查询,每个查询一个x,问最多能有多少点满足这些点中,最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。

思路:可以三遍bfs处理出所有点的d…

由于不能排序。。。所以就是尺取+rmq….

然而神Tm TLE…..

这复杂度还TLe…

结果最后发现是。。。log运算的常数太大被卡。。。

2016-07-17 23-19-46 的屏幕截图 2016-07-17 23-26-58 的屏幕截图

 

所以做法是先预处理一下。。。嗯。。。。

 

珍爱生命,远离log!

珍爱生命,远离log!

珍爱生命,远离log!

 

 

 

POJ 1849 Two (树的直径)

题目链接

题意:一棵树。。然后初始两个推雪机在点s,问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少(走过一条有雪的边和一条没雪的边耗费的汽油一样)

 

思路:很容易想到,我们应该尽可能不走已经被清理过雪了的边,因为这样很浪费。。。这样不难想到应该是和树的直径有关。但是初始的位置是给定的。。。怎么办?突然发现由于是给了两个推雪机。。所以其实相当于。。。只有一个推雪机&我们可以从任意位置开始推雪。。。第二个问题是。。。对于不在直径上的边。。我们怎么算cost?解决办法是读边的时候进行记录。。。然后求直径的时候记录路径。。。对于一条边。。。只要有一个点不在直径上。。。那么这条边的代价就是2倍。。。

1A蛤蛤蛤

 

 

hdu 4607 Park Visit (树的直径,推公式)

hdu4607题目链接
题意:给出一棵树。。。边权都为1. m个查询。。每个查询给一个k,表示只访问k个点。。。问每次的最小路径和是多少。。。
思路:我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何(深度的意思是说,与和该点最近的直径上的点的距离),距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d,那么k<=d+1的时候,答案为k-1,否则答案为d+(k-d-1)*2。。。

因为bfs的时候忘记标记起点WA了一发蠢哭。。。。2A

 

 

 

poj 3310 Caterpillar (树的直径+并查集判环+dfs判断连通性)

poj3310 题目链接

题意:给出一个无向图。。。问是否满足。。联通,并且无环,并且能找到一条路径,图中所有的顶点要么在这条路径上,要么与这条路径上的顶点相邻。

思路:一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过

环的话并查集就好。。

关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长?

于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。

具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一个to[]数组表示相连。。。to[u]=v,to[v]=u…

然后只要ok[i]或者ok[to[i]]满足其一就好。。。

又是1A,蛤蛤蛤蛤蛤,我好神啊(误

 

 

 

 

hdu 4514 湫湫系列故事——设计风景线 (无向图并查集判环+非联通图的最长路径)

hdu4514

题意:给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。

思路:无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。

但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。

也就是要在一个不联通的图中求最长路径。。。

没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。

不过感觉最容易想到的还是求多次直径的做法。。。

也就是。。每一个联通块求一次直径。。。取最大。。。

具体做的时候。。。加一个bool数组在bfs标记一下就好。。。

以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注意d数组初始化的问题。。。不能初始化成0x3f…(这么说来即使联通也没必要初始化成0x3f。。。。)

还有一点,这道题数据量比较大。。。用vector存图会MLE …

 

 

 

 

 

hdu 2196 Computer (树的直径||树形dp)

hdu2196

题意:给出一棵树。。。求距离每个点的最远距离是多少。。。

思路:最远距离什么的。。能想到树的直径。。。但是有什么关系呢? 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。?

1A.

 

 

20161201upd:更新一个dp的做法(虽然用树的直径搞貌似要更好想也更直观,不过为了体会dp的思想嘛。。。)

参考题解

 这道题要求的是从树上一点出发的最长路。考虑有根树,不难想到,从树上一点u出发的最长路必然是下述两种情况之一:
(1)第一步向下走,(一直向下,走到某叶子节点)
(2)第一步向上走。
考虑树形DP:
dp[0][u] : 从节点u向下走的最长路径
dp[1][u] : 从节点u向下走的次长路径
这里,次长路径的含义是:与某条选定的最长路径不重合的路径中最长的路径。
dp[2][u] : 从节点u第一步向上走所能获得的最长路径
注意:

考虑如何转移
对于节点u,考虑u的所有子节点v,用dp[0][v]来更新dp[0][u], dp[1][u]。
至于dp[2][u], 仍考虑两种情况:
(1)第二步向下走, 这样便转移到u的父亲节点f第一步向下走的情况。
这时还要考虑用dp[0][f]还是dp[1][f]来更新dp[2][u]:(kk:因为如果第一步向上走,然后又从父亲节点回到当前节点,那么这是无意义,并且等于没有更新向上走的情况,这也是要求次小的原因)如果从f第一步走到u能走出一条从f向下的最长路,就用dp[1][f]来更新dp[2][u],否则用dp[0][f]。
(2)第二步仍向上走,这样便转移到f第一步向上走的情况,即dp[2][f]。

 

 

poj 2631 Roads in the North (树的直径)

poj2631
题意:一棵树中求两个点的最远距离。。。
思路:就是求树的直径。。。裸体。。。。1A

poj 1985 Cow Marathon (树的直径模板题)

poj1985
题意:求树上两点的最长距离。。。也就是传说中的树的直径。。。

思路: 两遍BFS :先任选一个起点BFS找到最长路的终点,再从终点进行BFS,则第二次BFS找到的最长路即为树的直径;
原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
证明: 1) 如果u 是直径上的点,则v显然是直径的终点(因为如果v不是的话,则必定存在另一个点w使得u到w的距离更长,则于BFS找到了v矛盾)
2) 如果u不是直径上的点,则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
所以v一定是直径的一个端点,所以从v进行BFS得到的一定是直径长度

 

参考博客

 

实际写的时候,第一次bfs最后一个出队的点就是直径的一个端点。。。

好像错了。。。还是稳妥一点。。。最后扫一遍。。距离最远的一定是端点。。。
然后因为题目没有数据范围。。。?re多次orz。。。