POJ 1985 Cow Marathon（树的直径）

本文主要是介绍POJ 1985 Cow Marathon（树的直径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
题意：给出一棵树，求出这个树的直径
解答：任选一点进行dfs，会找到一个最远点s，在以这个最远点s进行dfs，会找到一个最远点是t，那么s-t就是树的直径。

//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define LL long long
#define pb push_back
#define P pair<int,int>
#define cl(a,b) memset(a,b,sizeof(a))
const int maxn=50000;
const int inf=1<<27;struct node{int v,w;node(){}node(int a,int b):v(a),w(b){}
};
int sum,p;
bool vis[maxn];
vector<node> mp[maxn];
void dfs(int u,int dis){if(dis>sum)sum=dis,p=u;vis[u]=true;for(int i=0;i<mp[u].size();i++){int v=mp[u][i].v;if(vis[v])continue;dfs(v,dis+mp[u][i].w);}
}
int main(){int n,m;while(~scanf("%d%d",&n,&m)){for(int i=0;i<m;i++){int u,v,w;char op[12];scanf("%d%d%d%s",&u,&v,&w,op);mp[u].pb(node(v,w));mp[v].pb(node(u,w));}sum=0;p=0;cl(vis,false);dfs(1,0);sum=0;cl(vis,false);dfs(p,0);printf("%d\n",sum);for(int i=0;i<maxn;i++)mp[i].clear();}return 0;
}

这篇关于POJ 1985 Cow Marathon（树的直径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---