题意:有n(1<=n<=2500)个点的树,每条边有一定的权值,定义P(T)为树T中任意两点之间距离的最大值,现在有一个人有一种魔法能改变其中一条边
连接的点对,形成一个新树,问形成的所有新树中P(T)的最小值。
题解:首先可以肯定的是选中的边一定是直径中的一条边,否则直径不变。现在就是将选中的边放在那里的问题,枚举去掉直径上的边形成两颗子树,在两个
子树分别求直径d1,d2,然后分别求出直径上的点v(假设直径为a->b),使得ABS(len(av) - len(vb))最小,那么将当前边加在v->vv之间最优,
然后用MAX(d1 , d2 , MAX(len(av) ,len(vb))+ v->vv + MAX(len(avv) - len(vvb)))更新答案即可。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> #define MIN(a , b) ((a) < (b) ? (a) : (b)) #define MAX(a , b) ((a) > (b) ? (a) : (b)) using namespace std; const int inf = 1 << 29; const int maxn = 2502; struct node { int v,w; int next; }edge[maxn << 1]; int head[maxn],dp[maxn][2],son[maxn][2],E[maxn]; bool vis[maxn]; int n,idx,here,top; void init() { memset(head,-1,sizeof(head)); idx = top = 0; return; } void addedge(int u,int v,int w) { edge[idx].v = v; edge[idx].w = w; edge[idx].next = head[u]; head[u] = idx++; edge[idx].v = u; edge[idx].w = w; edge[idx].next = head[v]; head[v] = idx++; return; } void read() { scanf("%d",&n); int u,v,w; for(int i=1;i<n;i++) { scanf("%d %d %d",&u,&v,&w); addedge(u,v,w); } return; } void dfs(int st,int pre) { vis[st] = true; for(int i=head[st];i != -1;i=edge[i].next) { if(edge[i].v == pre) continue; dfs(edge[i].v , st); int tmp = edge[i].w + dp[edge[i].v][0]; if(tmp > dp[st][0]) { dp[st][1] = dp[st][0]; son[st][1] = son[st][0]; dp[st][0] = tmp; son[st][0] = i; } else if(tmp > dp[st][1]) { dp[st][1] = tmp; son[st][1] = i; } } return; } int select(int u,int v) { memset(dp,0,sizeof(dp)); memset(son,-1,sizeof(son)); memset(vis,false,sizeof(vis)); int diameter = -1; dfs(u,v); for(int i=0;i<n;i++) { if(vis[i] && dp[i][0] + dp[i][1] > diameter) { diameter = dp[i][0] + dp[i][1]; here = i; } } return diameter; } int fuck(int d,int st) { int res = d; int center = st; while(son[st][0] != -1) { res = MIN(res , MAX(dp[st][0] , d - dp[st][0])); st = edge[son[st][0]].v; } st = center; if(son[st][1] != -1) { res = MIN(res , MAX(dp[st][1] , d - dp[st][1])); st = edge[son[st][1]].v; while(son[st][0] != -1) { res = MIN(res , MAX(dp[st][0] , d - dp[st][0])); st = edge[son[st][0]].v; } } return res; } void solve() { select(0,-1); int d = son[here][0]; while(d != -1) { E[top++] = d; d = son[edge[d].v][0]; } d = son[here][1]; while(d != -1) { E[top++] = d; d = son[edge[d].v][0]; } int ans = inf; for(int i=0;i<top;i++) { int id = E[i]; int v = edge[id].v; int u = edge[id^1].v; int dl = select(u,v); if(dl > ans) continue; int l = fuck(dl , here); int dr = select(v,u); if(dr > ans) continue; int r = fuck(dr , here); d = MAX(dl , dr); ans = MIN(ans , MAX(d , l + r + edge[id].w)); } printf("%d\n",ans); return; } int main() { int cas; scanf("%d",&cas); for(int i=1;i<=cas;i++) { printf("Case %d: ",i); init(); read(); solve(); } return 0; }