【树的直径】 POJ 1985 Cow Marathon

给出一棵树 ，和边的权值

求权值最长的一条直径

两次bfs求

第一次以任意点开始 BFS求出第一个端点

第二次以第一次得到的端点 BFS求出第二个端点

#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <cctype> #include <cmath> #include <string> #include <sstream> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> typedef long long LL; typedef long double LD; #define pi acos(-1.0) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 typedef pair<int, int> PI; typedef pair<int, PI> PP; #ifdef _WIN32 #define LLD "%I64d" #else #define LLD "%lld" #endif const int MAXN = 200100; const int INF = 999999; //LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;} //inline int read(){char ch=' ';int ans=0;while(ch<'0' || ch>'9')ch=getchar();while(ch<='9' && ch>='0'){ans=ans*10+ch-'0';ch=getchar();}return ans;} //inline void print(LL x){printf(LLD, x);puts("");} //inline void read(int &x){char c = getchar();while(c < '0') c = getchar();x = c - '0'; c = getchar();while(c >= '0'){x = x * 10 + (c - '0'); c = getchar();}} struct Edge {int to,next,val; } edge[MAXN*2]; int head[MAXN],d[MAXN],tol; bool vis[MAXN]; void init() {tol=0;memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) {edge[tol].to=v,edge[tol].val=w,edge[tol].next=head[u];head[u]=tol++;edge[tol].to=u,edge[tol].val=w,edge[tol].next=head[v];head[v]=tol++; } int bfs(int u) {int point,big=0;memset(vis,false,sizeof(vis));queue<int>q;q.push(u);vis[u]=true;d[u]=0;while(!q.empty()){u=q.front();q.pop();for(int i=head[u]; ~i; i=edge[i].next){int v=edge[i].to;if(!vis[v]){d[v]=d[u]+edge[i].val;if(d[v]>big){big=d[v];point=v;}vis[v]=true;q.push(v);}}}return point; } int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); #endifint t,a,b,c,n,m;while(scanf("%d%d",&n,&m)!=EOF){init();for(int i=0; i<m; i++){scanf("%d%d%d %*c",&a,&b,&c);addedge(a,b,c);}int u=bfs(1);int v=bfs(u);int len=d[v];cout<<len<<endl;}return 0; }

转载于:https://www.cnblogs.com/kewowlo/p/4088333.html

总结

以上是生活随笔为你收集整理的【树的直径】 POJ 1985 Cow Marathon的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。