Problem: [Usaco2004Feb]Cow Maratho

Time Limit: 1 Sec Memory Limit: 128 MB

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 createa bovine marathon for his cows to run. The marathon route willinclude a pair of farms and a path comprised of a sequence of roadsbetween them. Since Farmer John wants the cows to get as much exercise aspossible he wants to find the two farms on his map that are thefarthest ap art from each other (distance being measured in termsof total length of road on the path between the two farms). Helphim determine the distances between this farthest pair of farms.在听到美国肥胖的流行后，农夫约翰希望他的牛能得到更多的锻炼，所以他致力于为他的牛创造一个马拉松比赛。马拉松路线将包括一对农场和一条由它们之间的一系列道路组成的道路。由于农夫约翰希望奶牛尽可能多地运动，他想在地图上找到两个彼此最接近的农场（以两个农场之间的道路总长度为单位测量距离）。帮助他确定这对最远的农场之间的距离。

Input

Lines 1…: Same input format as “Navigation Nightmare”.

Output

Line 1: An integer giving the distance between the farthest pair of
farms.

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

OUTPUT DETAILS:

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.
Hint
由于是无向图，找出图中距离最大的两个点，就能得出最大距离。最容易想到的方法就是，先从一个随意给定的点（记为a）进行深度搜索，找到一个距离a最远的点（记为b）——很明显用宽搜很容易就能达到这一目标。此时，只要将点b记为初始点，再进行一次宽度搜索，此时就能找出的离点b最远的点（记为点c）。而b，c之间的距离，即图中任意两点之间最大的距离。

代码如下

#include<stdio.h>
#include<string.h>
int f[40001][6];
int d[40001][5],ans=0,maxx=-1,maxi,l,c,ansi,use[40001];
char aa;
void find(int s,int len)  {
	if (len>ans)     {
		ans=len;
		ansi=s;
	}
	int i=1;
	while(i<=f[s][0]) {
		if(use[f[s][i]]) {
			use[f[s][i]]=0;
			int y=d[s][i];
			find(f[s][i],len+y);
			use[f[s][i]]=1;
		}
		i++;
	}
}
int main() {
	int m,n,a,b,c;
	memset(use,1,sizeof(use));
	scanf("%d %d",&m,&n);
	int i=1;
	while(i<=n) {
		scanf("%d %d %d %c",&a,&b,&c,&aa);
		f[a][0]++;
		f[a][f[a][0]]=b;
		d[a][f[a][0]]=c;
		f[b][0]++;
		f[b][f[b][0]]=a;
		d[b][f[b][0]]=c;
		i++;
	}
	use[1]=0;
	find(1,0);
	memset(use,1,sizeof(use));
	ans=0;
	find(ansi,0);
	printf("%d",ans);
	return 0;
}