Rday1

Rday1

树的直径

Roads in the North

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

题解
首先分析题意,表示的是一个村落到另一个村落的距离并且带有权值,自然可以想到并查集或者树的直径,再加上所求的是最远的两个村落之间的最大的费用,可以知道,这道题就是求树的直径
树的直径做法:跑两边BFS就可以了,其中BFS表示找到一端的端点
整体做法:先vector存图,然后用队列和pair来写BFS,这个和模板有点相识,运用相关思想可解

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<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5;
bool vis[maxx];
int dis[maxx];
int en;
int ans;
vector<pair<int, int> >v[maxx];
int bfs(int x)
{
queue<int> q;
memset(vis, 0, sizeof vis);
memset(dis, 0, sizeof dis);
vis[x] = 1;
q.push(x);
en = 0;
ans = 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] = t.second + dis[f];
q.push(t.first);
}
}
}
return en;
}
int main()
{
int n, m, k;
for(int i = 0; i < v[i].size(); i ++) v[i].clear();
while(scanf("%d %d %d",&n, &m, &k)!=EOF)
{
v[n].push_back(make_pair(m, k));
v[m].push_back(make_pair(n, k));
}
bfs(1);
bfs(en);
printf("%d\n",ans);

return 0;
}

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