題意：
? ? ? 給你一棵樹，讓你改變一條邊，改變之后依然是一棵樹，然后問你怎樣改變才能讓樹的直徑最短。這里的改變一條邊指的是指把一條邊長度不變，連在別的兩個點上。


思路：

? ? ? 首先求出樹的直徑，把直徑上的邊記錄下來，然后在枚舉這些邊（枚舉別的邊沒意義）每次枚舉我的做法是后建造兩棵樹，我們只要在這兩棵樹之間連接一條邊就行了，但是怎么連接呢？ 我是先沒別求兩棵樹的直徑，然后在找到直徑上中間點，然后連接這兩棵樹的中間點，只有這樣才能保證最短，每次連接后的直徑就是 兩棵樹的直徑，和當前枚舉的邊長度+兩個樹被中間點分開的較長的那一個值的和，他們三個中較長的哪一個，就這樣在所有中找到一個最小的就是答案。

#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 树的最小直径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。