hdu 3721 树的最小直径

题意：

给你一棵树，让你改变一条边，改变之后依然是一棵树，然后问你怎样改变才能让树的直径最短。这里的改变一条边指的是指把一条边长度不变，连在别的两个点上。

思路：

首先求出树的直径，把直径上的边记录下来，然后在枚举这些边（枚举别的边没意义）每次枚举我的做法是后建造两棵树，我们只要在这两棵树之间连接一条边就行了，但是怎么连接呢？我是先没别求两棵树的直径，然后在找到直径上中间点，然后连接这两棵树的中间点，只有这样才能保证最短，每次连接后的直径就是两棵树的直径，和当前枚举的边长度+两个树被中间点分开的较长的那一个值的和，他们三个中较长的哪一个，就这样在所有中找到一个最小的就是答案。

#include<stdio.h>

#include<string.h>

#include<queue>

#include<map>

#define N_node 2500 + 5

#define N_edge 5000 + 5

#define INF 1000000000



using namespace std;

typedef struct

{

   int to ,next ,cost;

}STAR;

typedef struct

{

   int a ,b ,c;

}EDGE;

STAR E[N_edge];

EDGE edge[N_node];

int list[N_node] ,tot;

int s_x[N_node] ,mer[N_node];

map<int ,map<int ,int> >hash;

void add(int a ,int b ,int c)

{

   E[++tot].to = b;

   E[tot].cost = c;

   E[tot].next = list[a];

   list[a] = tot;

   E[++tot].to = a;

   E[tot].cost = c;

   E[tot].next = list[b];

   list[b] = tot;

}

void Spfa(int s ,int n)

{

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

   s_x[i] = INF ,mer[i] = i;

   int mark[N_node] = {0};

   s_x[s] = 0 ,mark[s] = 1;

   queue<int>q;

   q.push(s);

   while(!q.empty())

   {

      int xin ,tou;

      tou = q.front();

      q.pop();

      mark[tou] = 0;

      for(int k = list[tou] ;k ;k = E[k].next)

      {

         xin = E[k].to;

         if(s_x[xin] > s_x[tou] + E[k].cost)

         {

            s_x[xin] = s_x[tou] + E[k].cost;

            mer[xin] = tou;

            if(!mark[xin])

            {

               mark[xin] = 1;

               q.push(xin);

            }

         }

      }

   }

   return ;

}

int abss(int x)

{

   return x > 0 ? x : -x;

}

int maxx(int x ,int y)

{

   return x > y ? x : y;

}

int main ()

{

   int t ,n ,a ,b ,c ,i ,j;

   int cas  = 1;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d" ,&n);

      memset(list ,0 ,sizeof(list));

      tot = 1;

      for(i = 1 ;i < n ;i ++)

      {

         scanf("%d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);

         edge[i].a ++ ,edge[i].b ++;

         add(edge[i].a ,edge[i].b ,edge[i].c);

      }

      int p01 ,p02;

      Spfa(1 ,n);

      int maxxx = -1;

      for(j = 1 ;j <= n ;j ++)

      if(maxxx < s_x[j] && s_x[j] != INF)

      {

         maxxx = s_x[j];

         p01 = j;

      }

      Spfa(p01 ,n);

      maxxx = -1;

      for(j = 1 ;j <= n ;j ++)

      if(maxxx < s_x[j] && s_x[j] != INF)

      {

         maxxx = s_x[j];

         p02 = j;

      }

      int x = p02;

      hash.clear();

      while(x != mer[x])

      {

         hash[x][mer[x]] = hash[mer[x]][x] = 1;

         x = mer[x];

      }

      int ans = INF;

      for(i = 1 ;i < n ;i ++)

      {

         if(!hash[edge[i].a][edge[i].b]) continue;

         memset(list ,0 ,sizeof(list)) ,tot = 1;

         for(j = 1 ;j < n ;j ++)

         if(j == i) continue;

         else add(edge[j].a ,edge[j].b ,edge[j].c);

         int p11 ,p12 ,mid1 ,l1 ,mid1l;

         Spfa(edge[i].a ,n);

         int max = -1;

         for(j = 1 ;j <= n ;j ++)

         if(max < s_x[j] && s_x[j] != INF)

         {

            max = s_x[j];

            p11 = j;

         }

         Spfa(p11 ,n);

         max = -1;

         for(j = 1 ;j <= n ;j ++)

         if(max < s_x[j] && s_x[j] != INF)

         {

            max = s_x[j];

            p12 = j;

         }

         l1 = max;

         int x = p12;

         int min = INF;

         while(x != mer[x])

         {

            if(min > abss(s_x[x] - (l1 - s_x[x])))

            {

               min = abss(s_x[x] - (l1 - s_x[x]));

               mid1 = x;

               mid1l = maxx(s_x[x] ,l1 - s_x[x]);

            }

            x = mer[x];

         }

         if(min > abss(s_x[x] - (l1 - s_x[x])))

         {

            min = abss(s_x[x] - (l1 - s_x[x]));

            mid1 = x;

            mid1l = maxx(s_x[x] ,l1 - s_x[x]);

         }

         int p21 ,p22 ,mid2 ,l2 ,mid2l;

         Spfa(edge[i].b ,n);

         max = -1;

         for(j = 1 ;j <= n ;j ++)

         if(max < s_x[j] && s_x[j] != INF)

         {

            max = s_x[j];

            p21 = j;

         }

         Spfa(p21 ,n);

         max = -1;

         for(j = 1 ;j <= n ;j ++)

         if(max < s_x[j] && s_x[j] != INF)

         {

            max = s_x[j];

            p22 = j;

         }

         l2 = max;

         x = p22;

         min = INF;

         while(x != mer[x])

         {

            if(min > abss(s_x[x] - (l2 - s_x[x])))

            {

               min = abss(s_x[x] - (l2 - s_x[x]));

               mid2 = x;

               mid2l = maxx(s_x[x] ,l2 - s_x[x]);

            }

            x = mer[x];

         }

         if(min > abss(s_x[x] - (l2 - s_x[x])))

         {

            min = abss(s_x[x] - (l2 - s_x[x]));

            mid2 = x;

            mid2l = maxx(s_x[x] ,l2 - s_x[x]);

         }

         int now = maxx(maxx(l1 ,l2) ,edge[i].c + mid1l + mid2l);

         if(ans > now) ans = now;

      }

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

   }

   return 0;

}

巴特西

hdu 3721 树的最小直径

最新文章

热门文章