1 /* 2 題目大意：給n個點n-1條邊的樹，求刪除哪條邊時兩個樹中最大的直徑與邊權的乘積最小。 3 樹的直徑(Diameter)是指樹上的最長簡單路。 4 直徑的求法：兩遍BFS (or DFS) 5 若刪除的邊不是直徑上的那么花費為max_len*wi 6 若刪除的邊是直徑上的那么花費為max(dp[u][2],dp[v][2])*wi 7 */ 8 #pragma comment(linker, "/STACK:16777216") 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <vector> 13 using namespace std; 14 15 const int maxn=100005; 16 int dep[maxn],ans[maxn],father[maxn],max_len;//ans下標對應邊的編號 17 int dp[maxn][3];//j=0存i節點的到子樹中的最長路，j=1存次長路，j=2存直徑 18 bool vis[maxn];//標記是否為直徑上的點 19 inline int max(int a,int b){return a>b?a:b;} 20 struct node 21 { 22 int id,w,v; 23 node(int id=0,int w=0,int v=0):id(id),w(w),v(v){} 24 }; 25 vector<node> f[maxn]; 26 27 void dfs_dep(int u,int pre)//找最長路 28 { 29 for(int i=0;i<f[u].size();i++) 30 { 31 int v=f[u][i].v; 32 if(v==pre) continue; 33 dep[v]=dep[u]+1; 34 father[v]=u; 35 dfs_dep(v,u); 36 } 37 return ; 38 } 39 40 void dfs(int u,int pre) 41 { 42 dp[u][0]=dp[u][1]=dp[u][2]=0; 43 for(int i=0;i<f[u].size();i++) 44 { 45 int v=f[u][i].v; 46 if(v==pre) continue; 47 dfs(v,u); 48 int temp=dp[v][0]+1; 49 if(temp>dp[u][0]) 50 { 51 dp[u][1]=dp[u][0];dp[u][0]=temp; 52 } 53 else if(temp>dp[u][1]) 54 dp[u][1]=temp; 55 dp[u][2]=max(dp[u][2],dp[v][2]);//u在子樹直徑邊上與不再直徑邊上 56 } 57 dp[u][2]=max(dp[u][2],dp[u][0]+dp[u][1]);//u在子樹直徑中與不再直徑中 58 } 59 60 void solve(int u,int pre) 61 { 62 for(int i=0;i<f[u].size();i++) 63 { 64 int v=f[u][i].v,id=f[u][i].id,w=f[u][i].w; 65 if(v==pre) continue; 66 solve(v,u); 67 //在樹的直徑上 68 if(vis[u] && vis[v]) 69 ans[id]=max(ans[id],w*dp[v][2]); 70 else ans[id]=w*max_len; 71 } 72 } 73 74 int main() 75 { 76 int t,i,n,icase=0,a,b,w; 77 scanf("%d",&t); 78 while(t--) 79 { 80 scanf("%d",&n); 81 for(i=1;i<=n;i++) f[i].clear(); 82 for(i=1;i<n;i++) 83 { 84 scanf("%d%d%d",&a,&b,&w); 85 f[a].push_back(node(i,w,b)); 86 f[b].push_back(node(i,w,a)); 87 } 88 int st,ed=1,temp; 89 dfs_dep(ed,-1); 90 for(i=1;i<=n;i++) 91 if(dep[ed]<dep[i]) ed=i; 92 dep[st=ed]=0; 93 dfs_dep(st,-1); 94 ed=st; 95 for(i=1;i<=n;i++) 96 if(dep[ed]<dep[i]) ed=i; 97 max_len=dep[ed]; 98 memset(vis,0,sizeof(vis)); 99 father[st]=-1;temp=ed; 100 while(father[temp]!=-1) 101 vis[temp]=true,temp=father[temp]; 102 memset(ans,0,sizeof(ans)); 103 dfs(st,-1);solve(st,-1); 104 dfs(ed,-1);solve(ed,-1); 105 temp=1; 106 for(i=1;i<n;i++) 107 if(ans[i]<ans[temp]) temp=i; 108 printf("Case #%d: %d\n",++icase,temp); 109 } 110 return 0; 111 }

?

轉載于:https://www.cnblogs.com/xiong-/p/4141895.html

總結

以上是生活随笔為你收集整理的hdu 4679 树的直径的全部內容，希望文章能夠幫你解決所遇到的問題。

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