UVA10308 Roads in the North 题解（博客搬家）

因为从一个村庄到另一个村庄时，同一个的村庄不会经过两次，所以村庄和路其实就是一棵无根树，用$dfs$ 找到结点 $a$ 的子结点到 $a$ 的最大距离再加上次大距离即可。找到的数的值就是树的直径。 也可以先从任意点 $a$ 一遍 $bfs$ 找到离当前点最远的点 $b$，再从该点再 $bfs$ 一遍找到离该点最远的点 $c$。点 $b$ 到点 $c$ 之间的距离即为所求。 （其实两种方法都是求树的直径） 就是输入格式真的毒瘤，在输入上调了好久。 代码： 1.dfs 做法

#include<vector> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> using namespace std; struct node{ int v,w; }; vector<node> edge[10001]; int ans; inline int dfs(register int x,register int y){ register int sum,num=0,i,v; for(i=0;i<edge[x].size();i++){ v=edge[x][i].v; if(v!=y){ sum=dfs(v,x)+edge[x][i].w; ans=max(ans,sum+num); num=max(num,sum); } } return num; } int main(){ string s; stringstream ss; register int i,a,b,c; while(getline(cin,s)){ ans=0; for(i=0;i<=10000;i++) edge[i].clear(); ss.clear(); ss.str(s); while(ss>>a>>b>>c){ edge[a].push_back((node){b,c}); edge[b].push_back((node){a,c}); getline(cin,s); ss.clear(); ss.str(s); } dfs(1,0); printf("%d\n",ans); } return 0; }

2.bfs 做法

#include<queue> #include<vector> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> using namespace std; struct node{ int to,nex,w; }edge[40039]; int ans,cnt,t; int head[10039],w[10039],vis[10039]; inline void add(int u,int v,int w){ edge[++cnt].nex=head[u]; edge[cnt].to=v; edge[cnt].w=w; head[u]=cnt; } inline void bfs(int x){ queue<int> q; q.push(x); vis[x]=1; register int i; while(!q.empty()){ int u=q.front(); q.pop(); for(i=head[u];i;i=edge[i].nex){ int v=edge[i].to; if(vis[v]==0){ w[v]=w[u]+edge[i].w; vis[v]=1; q.push(v); if(w[v]>ans){ ans=w[v]; t=v; } } } } } int main(){ string s; stringstream ss; register int i,a,b,c; while(getline(cin,s)){ cnt=0; memset(head,-1,sizeof(head)); ss.clear(); ss.str(s); while(ss>>a>>b>>c){ add(a,b,c); add(b,a,c); getline(cin,s); ss.clear(); ss.str(s); } memset(vis,0,sizeof(vis)); memset(w,0,sizeof(w)); ans=0; bfs(1); memset(vis,0,sizeof(vis)); w[t]=0; ans=0; bfs(t); printf("%d\n",ans); } return 0; }