BZOJ 3363: [Usaco2004 Feb]Cow Marathon 奶牛马拉松（树的直径）
Posted On 2018年4月18日
Description
最近美国过度肥胖非常普遍，农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松．马拉
松路线要尽量长，所以，告诉你农场的地图（该地图的描述与上题一致），请帮助约翰寻找两个
最远农场间的距离．
Input
第1行：两个分开的整数N和M.
第2到M+1行：每行包括4个分开的内容，Fi，F2，L，D分别描述两个农场的编号，道路的长
度，F1到F2的方向N，E，S，W．
Output
一个整数，表示最远两个衣场间的距离．
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
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
最长的马拉松路线从2通过4，1，6，3到5；总长为：20+3+12+9+7=52
最长的马拉松路线从2通过4，1，6，3到5；总长为：20+3+12+9+7=52
HINT
Source
Solution
2次dfs即可
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; inline int read() { register int f=1,k=0;register char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=2e6; struct mc{int too,nxt,val;}e[maxn<<1]; int last[maxn],dep[maxn],fa[maxn],root; ll ans,sum[maxn]; void dfs(const int cur) { for (int i=last[cur];i;i=e[i].nxt) if (e[i].too!=fa[cur]) fa[e[i].too]=cur,sum[e[i].too]=sum[cur]+e[i].val,dfs(e[i].too); sum[cur]>ans&&(ans=sum[cur],root=cur); } int main() { read();int m=read(); for (register int i=1,a,b,c;i<=m;i++) a=read(),b=read(),c=read(),getchar(), e[i<<1].too=b,e[i<<1|1].too=a,e[i<<1].nxt=last[a], e[i<<1|1].nxt=last[b],last[a]=i<<1,last[b]=i<<1|1,e[i<<1].val=e[i<<1|1].val=c; dfs(1); ans=0; memset(sum,0,sizeof(sum)); memset(fa,0,sizeof(fa)); dfs(root); printf("%lld\n",ans); } |
Subscribe
0 评论