Day8

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
本文字数： 14k | 阅读时长 ≈ 13 分钟

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# include <iostream>
# include <cstring>
# include <queue>
# include <vector>
const int maxn =100020;
using namespace std ;
int dis[maxn], ans ;
bool vis[maxn];
vector<pair<int ,int> > V[maxn];

int bfs(int x){
	memset(dis ,0 , sizeof(dis));
	memset(vis ,0 , sizeof(vis));
	queue<int > Q ;
	Q.push(x);
	vis[x]=1;
	int point=0;
	while (!Q.empty()){
		int F = Q.front();
		Q.pop();
		if(dis[F] > ans ){
			ans = dis[F];
			point = F;
		}
		pair <int ,int > t ;
		for (int i =0; i < V [F].size (); i ++){
			t = V[F][i];
			if(vis[t.first]==0){
				vis[t.first]=1;
				dis[t.first]=dis[F] + t.second ;
				Q.push (t.first);
			}
		}
	}
	return point;
}

int main(){
	int x,y,z ;
	输入
	ans=0;
	int point=bfs(1);
	ans=0;
	bfs(point);
	cout<<ans<<endl ;
	return 0;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Sample Input
2
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
Sample Output
Maximum rope length is 0.
Maximum rope length is 8.
Hint
Huge input, scanf is recommended.
If you use recursion, maybe stack overflow. and now C++/c 's stack size is larger than G++/gcc

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int mod = 1e9;
typedef long long ll;
int n, m;
char a[2000][3000];
int dis[2000][2000];
int ans;
int d[4][2] = {
	1, 0,
	-1, 0,
	0, 1,
	0, -1
};

struct node{
	int x, y;
}first, second;

void bfs(node first)
{
	ans = 0;
	memset(dis, -1, sizeof dis);
	queue<node> q;
	node e1, e2;
	e1.x = first.x, e1.y = first.y, dis[e1.x][e1.y] = 0;
	q.push(e1);
	while(!q.empty())
	{
		e1 = q.front();
		q.pop();

		for(int i = 0; i < 4; i ++)
		{
			e2.x = e1.x + d[i][0];
			e2.y = e1.y + d[i][1];
			if(e2.x >= 0 && e2.y >= 0 && e2.x < n && e2.y < m && a[e2.x][e2.y] != '#' && dis[e2.x][e2.y] == -1)
			{
				q.push(e2);
				dis[e2.x][e2.y] = dis[e1.x][e1.y] + 1;
				if(ans < dis[e2.x][e2.y])
				{
					ans = dis[e2.x][e2.y];
					second.x = e2.x;
					second.y = e2.y;
				}
			}
		}
	}
}


int main()
{
	int T;
	cin >> T;
	while(T --)
	{
		cin >> m >> n;
		for(int i = 0; i < n; i ++)
		{
			scanf("%s",&a[i]);
		}
		for(int i = 0; i < n; i ++)
		{
			for(int j = 0; j < m; j ++)
			{
				if(a[i][j] == '.')
				{
					first.x = i;
					first.y = j;
				}
			}
		}
		bfs(first);
		bfs(second);
		printf("Maximum rope length is %d.\n",ans);
	}

	return 0;
}

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
    12
    Sample 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
const int maxn = 5e5 + 10;//数组不要太大，不然会超时
using namespace std;
int dis[maxn];
int ans, en;
bool vis[maxn];
vector <pair<int,int> >V[maxn];
int bfs(int x)
{
	ans = 0;
	memset(dis,0,sizeof(dis));
 	memset(vis,0,sizeof(vis));
 	queue<int> q;
 	q.push(x);
	vis[x]=1;
 	en = 0;
 	while(!q.empty())
	{
 		int f = q.front();
 		q.pop();
 		if(dis[f] > ans)
		{
 			ans = dis[f];
			en = f;
		}
 		pair<int,int > t;
 		for(int i = 0; i < V[f].size();i ++)
		{
 			t = V[f][i];
 			if(vis[t.first] == 0)
			{
				vis[t.first] = 1;
 				dis[t.first] = dis[f] + t.second;
 				q.push(t.first);
 			}
 		}
 	}
 	return en;
}
int main ()
{
	int x, y, z;
	char c[100];
	int n, m;
	while(~scanf("%d %d",&m,&n))
	{
		for(int i = 0;i < n; i ++)
			V[i].clear();//注意每次用完vector之后要清空
		for(int i = 0; i < n; i ++)
		{
			scanf("%d %d %d %s",&x,&y,&z,&c);
			V[x].push_back(make_pair(y,z));
	 		V[y].push_back(make_pair(x,z));
		}
		bfs(1);
	 	bfs(en);
	 	cout << ans << endl;
	}
	return 0;
}

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
2
3
4
5
6
7
8
Sample Input
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
Sample Output
22

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
const int mod = 1e9;
const int maxx = 1e5 + 10;
typedef long long ll;
vector<pair<int, int> >v[maxx];
int ans;
bool vis[maxx];
int dis[maxx];
int en; //不要用end，是一个保留字
int bfs(int x)
{
	//每次bfs都要初始化
	ans = 0;
	memset(vis, 0, sizeof vis);
	memset(dis, 0, sizeof dis);
	//套用bfs模板
	queue<int> q;
	vis[x] = 1;
	q.push(x);
	en = 0;
	while(!q.empty())
	{
		int f = q.front();
		q.pop();
		//随着ans的不断更新，直到找到一个端点，标记下来
		if(dis[f] > ans)
		{
			ans = dis[f];
			en = f;//一段的开始
		}
		//创建新的数对，表示的是与v[]相连的点
		pair<int , int> p;
		//遍历所有地点 ，根据距离，寻找一端的点
		for(int i = 0; i < v[f].size(); i ++)
		{
			p = v[f][i];//表示 寻找这个点在图中的所有可能
			if(vis[p.first] == 0) //如果这个地点没有经过
			{
				vis[p.first] = 1;//先标记
				dis[p.first] = dis[f] + p.second;//加上距离 ，更新ans
				q.push(p.first);//入队，寻找这个点的所有可能性
			}
		}
	}
	return en;//将一端的标记返回出去

}


int main()
{
	int x, y, z;
	while(~scanf("%d %d %d",&x, &y, &z))
	{
		//存图，意思就是将与x,y相连的点和对应的权值存储起来，因为是双向的，所以权值一样
		v[x].push_back(make_pair(y, z));
		v[y].push_back(make_pair(x, z));
	}
	//第一次bfs随便找个点去找到整个图的一个端点
	bfs(1);
	//第二次bfs从一个端点出发去找另一个端点，即为树的直径
	bfs(en);
	//输出答案ans
	cout << ans << endl;

	return 0;
}
/*
题意：
有10000个村庄，有很多条路，现在这些路已经把村庄都连了起来，求最远的两个村庄的路的距离。

思路，把每一边都历遍一下，找到两个距离最远的村庄。

这里有一个结论，在图中，要找到距离最远的两点，先随便从一个点入手BFS，找到距离这个点最远的点，在从这个点BFS找到距离这点最远的点，这两点之间的距离就是这棵树的直径。所以直接进行BFS搜索就行了。
*/

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
2
3
4
5
6
7
8
9
10
11
12
13
14
Sample Input
5
1 1
2 1
3 1
1 1
Sample Output
3
2
3
4
4
提示
示例输入与此图对应。从图中，你可以看到计算机4离1最远，所以s1=3。计算机4和5是距离2最远的，所以s2=2。计算机5是离3最远的，所以s3=3。我们也得到了s4=4，s5=4。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>

using namespace std;
const int mod = 1e9;
const int maxx = 1e5 + 10;
typedef long long ll;
vector<pair<int, int> > v[maxx];
bool vis[maxx];
int dis[maxx];
int diss[maxx];
int ans;

int bfs(int x)
{
	ans = 0;
	memset(vis, 0, sizeof vis);
	memset(dis, 0, sizeof dis);
	queue<int> q;
	q.push(x);
	vis[x] = 1;
	int point;
	while(!q.empty())
	{
		int f = q.front();
		q.pop();
		if(ans < dis[f])
		{
			ans = dis[f];
			point = f;
		}
		for(int i = 0; i < v[f].size(); i ++)
		{
			if(vis[v[f][i].first] == 0)
			{
				vis[v[f][i].first] = 1;
				dis[v[f][i].first] = v[f][i].second + dis[f];
				q.push(v[f][i].first);
			}
		}
	}

	return point;
}



int main()
{
	int n;
	int a, b;
	while(~scanf("%d",&n))
	{
		for(int i = 0; i <= n; i ++) v[i].clear();
		for(int i = 1; i < n; i ++)
		{
			cin >> a >> b;
			v[i + 1].push_back(make_pair(a, b));
			v[a].push_back(make_pair(i + 1, b));
		}
		int point;
		point = bfs(bfs(1));
		for(int i = 1; i <= n; i ++) diss[i] = dis[i];
		bfs(point);
		for(int i = 1; i <= n; i ++)
		{
			cout << max(dis[i], diss[i]) << endl;
		}
	}
	return 0;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
Sample Input
2
4
0 1 20
1 2 30
2 3 50
5
0 2 20
2 1 10
0 3 29
0 4 50
Sample Output
Case 1: 100
Case 2: 80

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//e
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
const int maxn = 5e5 + 10;
using namespace std;
int dis[maxn];
int ans, en;
bool vis[maxn];
vector <pair<int,int> >V[maxn];
int bfs(int x)
{
	ans = 0;
	memset(dis,0,sizeof(dis));
 	memset(vis,0,sizeof(vis));
 	queue<int>q;
 	q.push(x);
	vis[x]=1;
 	en = 0;
 	while(!q.empty())
	{
 		int f = q.front();
 		q.pop();
 		if(dis[f] > ans)
		{
 			ans = dis[f];
			en = f;
		}
 		pair<int,int > t;
 		for(int i = 0; i < V[f].size();i ++)
		{
 			t = V[f][i];
 			if(vis[t.first] == 0)
			{
				vis[t.first] = 1;
 				dis[t.first] = dis[f] + t.second;
 				q.push(t.first);
 			}
 		}
 	}
 	return en;
}
int main ()
{
	int x, y, z;
	int T, n;
	cin >> T;
	int k = 1;
	while(T --)
	{
		cin >> n;
		for(int i = 0;i < n; i ++)
			V[i].clear();//注意每次用完vector之后要清空
		for(int i = 0; i < n - 1; i ++)
		{
			scanf("%d %d %d",&x,&y,&z);
			V[x].push_back(make_pair(y,z));
	 		V[y].push_back(make_pair(x,z));
		}
		bfs(0);
	 	bfs(en);
	 	printf("Case %d: %d\n",k ++, ans);
	}
	return 0;
}

---------------- The End ----------------
0%