UVa 11695 树的直径 Flight Planning

题意：

给出一棵树，删除一条边再添加一条边，求新树的最短的直径。

分析：

因为n比较小(n ≤ 2500)，所以可以枚举删除的边，分裂成两棵树，然后有这么一个结论：

合并两棵树后得到的新树的最短直径为：

$max\{ \left \lceil \frac{diameter(x)}{2} \right \rceil + \left \lceil \frac{diameter(y)}{2} \right \rceil+1, diameter(x), diameter(y)\}$

这两棵树一定是这样合并的，分别取两棵树直径的中点，然后将其连接起来。这样新树的直径才是最短的。

所以在找直径的同时还要记录下路径，方便找到中点。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int maxn =  + ;

 int n;

 struct Edge

 {

     int u, v, nxt;

     bool del;

 };

 Edge edges[maxn * ];

 int ecnt;

 int head[maxn];

 void AddEdge(int u, int v)

 {

     Edge& e = edges[ecnt];

     e.u = u;

     e.v = v;

     e.nxt = head[u];

     e.del = false;

     head[u] = ecnt++;

 }

 int pre[maxn];

 int len, id;

 void dfs(int u, int fa, int dep)

 {

     pre[u] = fa;

     if(dep > len) { len = dep; id = u; }

     for(int i = head[u]; ~i; i = edges[i].nxt)

     {

         if(edges[i].del) continue;

         int v = edges[i].v;

         if(v == fa) continue;

         dfs(v, u, dep + );

     }

 }

 int mid;

 int diameter(int u)

 {

     id = u;

     len = ;

     dfs(u, , );

     int s = id;

     len = ;

     dfs(s, , );

     mid = id;

     for(int i = ; i < len / ; i++) mid = pre[mid];

     return len;

 }

 int main()

 {

     int T; scanf("%d", &T);

     while(T--)

     {

         scanf("%d", &n);

         memset(head, -, sizeof(head));

         ecnt = ;

         for(int u, v, i = ; i < n; i++)

         {

             scanf("%d%d", &u, &v);

             AddEdge(u, v); AddEdge(v, u);

         }

         int ans = ;

         int del_u, del_v, add_u, add_v;

         for(int i = ; i < ecnt; i += )

         {

             Edge& e = edges[i];

             edges[i].del = true;

             edges[i^].del = true;

             int d1 = diameter(e.u), tu = mid;

             int d2 = diameter(e.v), tv = mid;

             int d3 = (d1 + ) /  + (d2 + ) /  + ;

             d1 = max(max(d1, d2), d3);

             if(d1 < ans)

             {

                 ans = d1;

                 del_u = edges[i].u;

                 del_v = edges[i].v;

                 add_u = tu;

                 add_v = tv;

             }

             edges[i].del = false;

             edges[i^].del = false;

         }

         printf("%d\n%d %d\n%d %d\n", ans, del_u, del_v, add_u, add_v);

     }

     return ;

 }

代码君

巴特西

UVa 11695 树的直径 Flight Planning

最新文章

热门文章