POJ1985Cow Marathon
题意：
给一个森林，求树的直径的最大值。
思路：
求树的直径的模板题。两次dfs(bfs)即可。 这篇博客讲的比较好。
代码：
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<ctype.h>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#define pii pair<int,int>
#define ll long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define INF 1e18
const int N
=1e6+10;
const int mod
=1e9+7;
const int inf
=0x3f3f3f3f;
const double eps
=1e-8;
const double pi
=acos(-1);
using namespace std
;
struct edge
{
int u
,v
,w
;
}e
[N
];
int head
[N
]={0},len
=0,mv
,ans
=0;
void add(int u
,int v
,int w
)
{
e
[++len
]={head
[u
],v
,w
};
head
[u
]=len
;
}
void dfs(int x
,int fa
,int dis
)
{
if(dis
>ans
)
{
ans
=dis
;
mv
=x
;
}
int i
;
for(i
=head
[x
];i
;i
=e
[i
].u
)
{
int v
=e
[i
].v
,w
=e
[i
].w
;
if(v
==fa
)
continue;
dfs(v
,x
,dis
+w
);
}
return;
}
int main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);cout
.tie(0);
int n
,m
,i
;
cin
>>n
>>m
;
for(i
=1;i
<=m
;i
++)
{
int u
,v
,w
;
char c
;
cin
>>u
>>v
>>w
>>c
;
add(u
,v
,w
);
add(v
,u
,w
);
}
dfs(1,0,0);
ans
=0;
dfs(mv
,0,0);
cout
<<ans
<<endl
;
return 0;
}
