Day8
树的直径->双重BFS/DFS跑图
学的效果整体还行
树
什么是树?
树(tree)是包含n(n>0)个结点的有穷集,其中:
每个元素称为结点(node);
有一个特定的结点被称为根结点或树根(root);
除根结点之外的其余数据元素被分为m(m≥0)个互不相交
的集合T1,T2,…Tm−1,其中每一个集合Tm−1(1≤i≤m)
本身也是一棵树,被称作原树的子树(subtree)。
树的直径的定义
树中距离最大的两个结点之间的距离称为树的直径。
求解方法
两次dfs或bfs。第一次任意选一个点进行dfs(bfs)找到离它最远的
点,此点就是最长路的一个端点,再以此点进行dfs(bfs),找到
离它最远的点,此点就是最长路的另一个端点,于是就找到了树
的直径。
证明
假设此树的最长路径是从s到t,我们选择的点为u。
反证法:假设搜到的点是v。
1、v在这条最长路径上,那么dis[u,v]>dis[u,v]+dis[v,s],显然矛
盾。
2、v不在这条最长路径上,我们在最长路径上选择一个点为po,
则dis[u,v]>dis[u,po]+dis[po,t],那么有dis[s,v]=dis[s,po]+dis[po,u]
+dis[u,v]>dis[s,po]+dis[po,t]=dis[s,t],即dis[s,v]>dis[s,t],矛盾。
也许你想说u本身就在最长路径,或则其它的一些情况,但其实
都能用类似于上面的反证法来证明的。
综上所述,你两次dfs(bfs)就可以求出最长路径的两个端点和路
径长度
相关题目
POJ 2631
POJ 1985
POJ 1383
带权图相关代码模板(用的时候要合理变动)
1 |
|
OJ链接:https://vjudge.net/contest/313488#overview
Labyrinth
Problem Description
The northern part of the Pyramid contains a very large and complicated labyrinth. The labyrinth is divided into square blocks, each of them either filled by rock, or free. There is also a little hook on the floor in the center of every free block. The ACM have found that two of the hooks must be connected by a rope that runs through the hooks in every block on the path between the connected ones. When the rope is fastened, a secret door opens. The problem is that we do not know which hooks to connect. That means also that the neccessary length of the rope is unknown. Your task is to determine the maximum length of the rope we could need for a given labyrinth.Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers C and R (3 <= C,R <= 1000) indicating the number of columns and rows. Then exactly R lines follow, each containing C characters. These characters specify the labyrinth. Each of them is either a hash mark (#) or a period (.). Hash marks represent rocks, periods are free blocks. It is possible to walk between neighbouring blocks only, where neighbouring blocks are blocks sharing a common side. We cannot walk diagonally and we cannot step out of the labyrinth.
The labyrinth is designed in such a way that there is exactly one path between any two free blocks. Consequently, if we find the proper hooks to connect, it is easy to find the right path connecting them.Output
Your program must print exactly one line of output for each test case. The line must contain the sentence “Maximum rope length is X.” where Xis the length of the longest path between any two free blocks, measured in blocks.
1 | Sample Input |
code:
1 |
|
Cow Marathon
Problem Description
After hearing about the epidemic of obesity in the USA, Farmer John wants his cows to get more exercise, so he has committed to create a bovine marathon for his cows to run. The marathon route will include a pair of farms and a path comprised of a sequence of roads between them. Since FJ wants the cows to get as much exercise as possible he wants to find the two farms on his map that are the farthest apart from each other (distance being measured in terms of total length of road on the path between the two farms). Help him determine the distances between this farthest pair of farms.
有n个农田和m条路,以及每条路的方向(方向在这道题中没有用),求最长的一条路,也就是两点间的最大距离,即树的直径.Input
- Lines 1…..: Same input format as “Navigation Nightmare”.
Output
- Line 1: An integer giving the distance between the farthest pair of farms.
1
2
3
4
5
6
7
8
9
10
11
12Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
Sample Output
52
Hint
The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.
code:
1 |
|
Roads in the North
Problem Description
Building and maintaining roads among communities in the far North is an expensive business. With this in mind, the roads are build such that there is only one route from a village to a village that does not pass through some other village twice.
Given is an area in the far North comprising a number of villages and roads among them such that any village can be reached by road from any other village. Your job is to find the road distance between the two most remote villages in the area.
The area has up to 10,000 villages connected by road segments. The villages are numbered from 1.Input
Input to the problem is a sequence of lines, each containing three positive integers: the number of a village, the number of a different village, and the length of the road segment connecting the villages in kilometers. All road segments are two-way.Output
You are to output a single integer: the road distance between the two most remote villages in the area.
1 | Sample Input |
code:
1 |
|
Computer
Problem Description
A school bought the first computer some time ago(so this computer’s id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.
Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.
Input
输入文件包含多组测试样例。在每组样例中,第一行中都有自然数n(n<=10000),然后是(n-1)行,其中包含对计算机的描述。第i行包含两个自然数-第i计算机所连接的计算机和用于连接的电缆长度。电缆总长度不超过10^9。输入行中的数字用空格分隔。Output
对于每组样例,输出n行。第i行第i台计算机的到其他计算机的最大长度Si(1<=i<=n)。
1 | Sample Input |
code:
1 |
|
Farthest Nodes in a Tree
Problem Description
Given a tree (a connected graph with no cycles), you have to find the farthest nodes in the tree. The edges of the tree are weighted and undirected. That means you have to find two nodes in the tree whose distance is maximum amongst all nodes.Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with an integer n (2 ≤ n ≤ 30000) denoting the total number of nodes in the tree. The nodes are numbered from 0 to n-1. Each of the next n-1 lines will contain three integers u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) denoting that node u and v are connected by an edge whose weight is w. You can assume that the input will form a valid tree.Output
For each case, print the case number and the maximum distance.
1 | Sample Input |
code:
1 | //e |