Photo by Nick Kwan from Pexels
这篇文章的主要目的是为了屯模板......
POJ1985 Cow Marathon 裸题，直接两边dfs求出直径即可（输入里面的那个方向是没用的......） 代码如下
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=50000;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node{
int to,next;
ll wei;
};
node es[maxn<<1];
int head[maxn+5];
int cnt;
ll dis[maxn];
void add(int u,int v,int wei)
{
es[cnt].to=v;
es[cnt].wei=wei;
es[cnt].next=head[u];
head[u]=cnt++;
}
void dfs(int st,int fa)
{
// dis[st]=dis[fa]+es[fa].wei;
for(int i=head[st];i!=-1;i=es[i].next){
int to=es[i].to;
if(to==fa) continue;
dis[to]=dis[st]+es[i].wei;
dfs(to,st);
}
}
int main()
{
IOS;
int n,m;
while(cin>>n>>m){
mst(head,-1);cnt=0;
mst(dis,0);
int start;
for(int i=0;i<m;i++){
int a,b,L;char dir;
cin>>a>>b>>L>>dir;
if(i==0) start=a;
add(a,b,L);add(b,a,L);
}
dfs(1,0);
int end_;ll ans=-1;
for(int i=1;i<=n;i++){
if(dis[i]>ans){
ans=dis[i];
end_=i;
}
}
// cout<<"end = "<<end_<<endl;
mst(dis,0);
dfs(end_,0);
ans=-1;
for(int i=1;i<=n;i++)
ans=max(ans,dis[i]);
cout<<ans<<endl;
}
return 0;
}对于每一个点，其最大距离即为直径的两个端点到该点的距离的较大值。
做法是跑三次bfs。第一次用于求出直径的一个端点；第二次从该端点出发找另一个端点，同时算出从该端点到其他点的距离；第三次从找出来的另一个端点出发算出它到其他点的距离。
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node{
int to;
int next,wei;
};
node es[80005];
int head[40005];
int cnt;
void add(int u,int v,int wei)
{
es[cnt].to=v;
es[cnt].wei=wei;
es[cnt].next=head[u];
head[u]=cnt++;
}
int dis1[40005];
int dis2[40005];
bool vis[40005];
int bfs1(int st)
{
queue<int> que;
que.push(st);
mst(vis,0);mst(dis1,0);
dis1[st]=0;vis[st]=1;
int maxi_len=dis1[st];
int point=0;
while(!que.empty()){
int now=que.front();
que.pop();
for(int i=head[now];i!=-1;i=es[i].next){
int to=es[i].to;
if(vis[to]==0){
vis[to]=1;
dis1[to]=dis1[now]+es[i].wei;
que.push(to);
if(maxi_len<dis1[to]){
maxi_len=dis1[to];
point=to;
}
}
}
}
return point;
}
int bfs2(int st)
{
queue<int> que;
que.push(st);
mst(vis,0);mst(dis2,0);
dis2[st]=0;vis[st]=1;
int maxi_len=dis2[st];
int point=0;
while(!que.empty()){
int now=que.front();
que.pop();
for(int i=head[now];i!=-1;i=es[i].next){
int to=es[i].to;
if(vis[to]==0){
vis[to]=1;
dis2[to]=dis2[now]+es[i].wei;
que.push(to);
if(maxi_len<dis2[to]){
maxi_len=dis2[to];
point=to;
}
}
}
}
return point;
}
int main()
{
int n;
// freopen("data_generator.txt","r",stdin);
// freopen("computer.txt","w",stdout);
while(scanf("%d",&n)!=EOF){
mst(head,-1);
for(int i=2;i<=n;i++){
int v,wei;
scanf("%d %d",&v,&wei);
add(i,v,wei);
add(v,i,wei);
}
int p1=bfs1(1);
int p2=bfs2(p1); //得到端点1到其他点的距离
bfs1(p2); //得到端点2到其他点的距离
for(int i=1;i<=n;i++)
printf("%d\n",max(dis1[i],dis2[i]));
}
return 0;
}