poj 1985 Cow Marathon 树的直径

缘起

学习树的直径 poj 1985 Cow Marathon

分析

所谓树的直径就是树这种图上距离最远的两个点. 而树是什么? 树的定义是递归的——

空集是（空）树，单点亦是树. 然后对于单点下面挂了若干子树构成的图亦是树

而算法导论上已经给出了求树的直径的算法

1
2
3
4
5
6
7
8
9
10
11
两趟bfs就可以得到树的直径.

第一趟bfs:
从树上任何一点出发(例如从根节点出发),通过bfs（因为抓住了树的特点——从树上任何一点到达
另外一点的路径是唯一的）可以求出所有其他点距离此点的距离（注意,这里我们可没说树的边权重恒为1）. 
求出最远的那个点P, 它必定是直径的一端. 这一点通过上述树的定义是不难知道成立的.

第二趟bfs
从P出发bfs，得到距离P最远的点必定是树的直径另一端.

经过上述两趟bfs, 我们得到了树的一条直径以及直径的长度.

上述算法可以见下图

下面来看本题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给你一棵树, 要你求直径.

【输入】
给出n和m, n是顶点的个数,m 是距离关系. 然后是m行. 每一行是形如
x y z E/S/W/N
E/S/W/N 是东南西北的意思, 表示x在y的某方位的z距离.

【输出】
最远距离

【样例输入】
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

【样例输出】
52

【限制】
2s

就是树的直径.（E/S/W/N其实并没有什么卵用）

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
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL
#include <queue>
#include <vector>
using namespace std;

const int maxn = 44000;
int n,m,ans,dis[maxn]; // dis[i]表示i距离目标点的距离
struct Node
{
	int to,dis; // 表示to这个点距离当前源的距离是dis
	Node(int to, int dis):to(to),dis(dis){}
};
vector<Node> g[maxn];
bool v[maxn];

typedef vector<Node>::iterator vit;

int bfs(int s) // 从树上的s出发进行bfs, 期间修改ans, 返回直径的一端
{
	int ansp;
	ans = 0;
	memset(v, 0, sizeof(v));
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	v[s] = true;
	while (!q.empty())
	{
		int front = q.front();
		q.pop();
		for (vit x = g[front].begin(); x!=g[front].end(); x++)
		{
			if (v[x->to])
			{
				continue;
			}
			v[x->to] = true;
			dis[x->to] = dis[front] + x->dis; // 抓住了树上两点之间的路径是唯一的
			q.push(x->to);
			if (dis[x->to]>ans)
			{
				ans = dis[x->to]; // 更新ans与ansp
				ansp = x->to;
			}
		}
	}
	return ansp; // 返回直径的一端
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	while(m--)
	{
		int a,b,c;
		char d;
		scanf("%d%d%d", &a, &b, &c);
		getchar(), getchar(); // 吸收一个空格一个方位字母
		g[a].push_back(Node(b,c)), g[b].push_back(Node(a,c));
	}
	int p  = bfs(1);
	bfs(p); // 两趟bfs确定树的直径
	printf("%d\n", ans);
	return 0;
}

ac情况（水过水过~ 好慢啊!）

Status Accepted
Time 1141ms
Memory 3060kB
Length 1277
Lang C++
Submitted 2019-09-10 06:51:51
Shared
RemoteRunId 20847554