poj 1383题目链接 题意：一个迷宫图，求最远两点的距离是多少，保证每两个点都是联通的。 思路：树的直径。 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> …

hdu 4123 题目链接 题意：一棵树，定义d[i]为点i到树上某点的最大距离。。。给出若干查询，每个查询一个x,问最多能有多少点满足这些点中，最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。 思路：可以三遍bfs处理出所有点的d... 由于不能排序。。。所以就是尺取+rmq.... 然而神Tm TLE..... 这复杂度还TLe... 结果最后发现是。。。log运算的常数太大被卡。。。 所以做法是先预处理一下。。。嗯。。。。 珍爱生命，远离log! 珍爱生命，远离log! 珍爱生命，远离log! /* *********************************************** Author …

题目链接 题意:一棵树。。然后初始两个推雪机在点s,问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少（走过一条有雪的边和一条没雪的边耗费的汽油一样） 思路：很容易想到，我们应该尽可能不走已经被清理过雪了的边，因为这样很浪费。。。这样不难想到应该是和树的直径有关。但是初始的位置是给定的。。。怎么办？突然发现由于是给了两个推雪机。。所以其实相当于。。。只有一个推雪机&我们可以从任意位置开始推雪。。。第二个问题是。。。对于不在直径上的边。。我们怎么算cost?解决办法是读边的时候进行记录。。。然后求直径的时候记录路径。。。对于一条边。。。只要有一个点不在直径上。。。那么这条边的代价就是2倍。。。 1A蛤蛤蛤 /* …

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

poj3310 题目链接 题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过 环的话并查集就好。。 关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长？ 于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。 具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一 …

hdu4514 题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。 思路：无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。 但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。 也就是要在一个不联通的图中求最长路径。。。 没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。 不过感觉最容易想到的还是求多次直径的做法。。。 也就是。。每一个联通块求一次直径。。。取最大。。。 具体做的时候。。。加一个bool数组在bfs标记一下就好。。。 以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注 …

hdu2196 题意：给出一棵树。。。求距离每个点的最远距离是多少。。。 思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？ 1A. /* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 13时29分49秒 File Name :code/hdu/2196.cpp …

poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A /* *********************************************** Author :111qqz Created Time :2016年07月12日 星期二 13时03分39秒 File Name :code/poj/2631.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

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最后一个出 …