【lightoj-1094】树的直径(DFS)

链接：http://www.lightoj.com/volume_showproblem.php?problem=1094

题意：

一共n各节点编号0-n-1，输入n-1条无向边代表u-v距离为w，求最远的两个点的距离（即树的直径）。

思路：

如果用最短路径来求，n<=30000是会超时的，正确做法是先随便从一个点开始深搜，搜到最远的节点一定是直径其中一个节点，然后从这个点再来次深搜。

 #include <bits/stdc++.h>

 using namespace std;

 const int N = ;

 vector<pair<int, int> >V[N];

 bool vis[N];

 int Index, ans;

 void dfs(int s, int sum)

 {

     vis[s] = ;

     if(ans < sum)

     {

         ans = sum;

         Index = s;

     }

     for(unsigned int i = ; i < V[s].size(); i++)

     {

         int v = V[s][i].first, w = V[s][i].second;

         if(vis[v]) continue;

         dfs(v, sum+w);

     }

 }

 int main()

 {

     int n, t, cas = ;

     cin>>t;

     while(t--)

     {

         scanf("%d", &n);

         int a, b, c;

         for(int i = ; i <= n; i++) V[i].clear();

         for(int i = ; i < n-; i++)

         {

             scanf("%d%d%d", &a, &b, &c);

             V[a].push_back(make_pair(b, c));

             V[b].push_back(make_pair(a, c));

         }

         ans = ;

         memset(vis, , sizeof vis);

         dfs(, );

         ans = ;

         memset(vis, , sizeof vis);

         dfs(Index, );

         printf("Case %d: %d\n", ++cas, ans);

     }

     return ;

 }

巴特西

【lightoj-1094】树的直径(DFS)

最新文章

热门文章