題目描述：
一顆有N個節點(N<2,500)的帶權樹。現在割去一條邊，加到其他節點上，并保證也是一棵樹。問最小的直徑是多少？
算法分析：
枚舉每條邊。樹形DP求出割掉這條邊后，每個節點可以到的最遠距離。
樹形DP是萬能的！！！！
#include<iostream>
#include<cstdio>
using namespace std;
// build graph
const int V = 2500 + 5;
const int E = V*2;
int head[V], nxt[E], pnt[E], cost[E], e, n;
void add(int u,int v,int c){
pnt[e] = v; cost[e] = c;
nxt[e] = head[u]; head[u] = e; e++;
}
// tree dp
const int inf = ~0u>>2;
int mx[V], sd[V];
void dfs(int u,int f){
mx[u]= 0;
sd[u] = 0;
for(int i = head[u]; i!=-1; i=nxt[i]) {
int v = pnt[i];
if(v == f) continue;
dfs(v,u);
if(cost[i] + mx[v] > mx[u]) {
sd[u] = mx[u];
mx[u] = cost[i] + mx[v];
}
else if(cost[i] + mx[v] > sd[u])
sd[u] = cost[i] + mx[v];
}
}
int temp, flag;
void dfs1(int u,int f) {
// cout<<"u: "<<u<<" "<<mx[u]<<" "<<sd[u]<<endl;
if(mx[u] < temp) temp = mx[u];
if(mx[u] > flag) flag = mx[u];
for(int i = head[u]; i!=-1; i=nxt[i]) {
int v = pnt[i];
if(v == f) continue;
// cout<<"v: "<<v<<" "<<mx[v]<<endl;
if(mx[v] + cost[i] < mx[u])
mx[v] = mx[u] + cost[i];
else if(cost[i] + sd[u] > mx[v]){
mx[v] = cost[i] + sd[u];
}
else if(cost[i] + sd[u] > sd[v]){
sd[v] = cost[i] + sd[u];
}
dfs1(v,u);
}
}
// main
int main(){
int test;
scanf("%d", &test);
for(int _ = 1; _ <= test; _ ++){
scanf("%d",&n);
int u,v,c;
//init
for(int i=0;i<n;i++) head[i] = -1;
e = 0;
// input
for(int i=1;i<n;i++) {
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
add(v,u,c);
}
int ans = inf;
for(int i=0;i<e;i+=2){
int u = pnt[i], v = pnt[i^1], mn = cost[i], mx1, mx2;
temp = inf;
flag = 0;
dfs(u,v); dfs1(u,v);
mn += temp;
mx1 = flag;
// cout<<temp<<endl;
temp = inf;
flag = 0;
dfs(v,u); dfs1(v,u);
mn += temp;
mx2 = flag;
mn = max(max(mx1,mx2),mn);
// cout<<temp<<endl;
if(mn < ans) ans = mn;
}
printf("Case %d: %d\n",_,ans);
}
}
posted on 2012-07-29 14:57
西月弦 閱讀(253)
評論(3) 編輯 收藏 引用