 /**//*
题意:给出一棵树,现可以移动一条边,问怎么移动使得最长边最小
n <= 2500

比赛时脑残,一点想法都没有
赛后火车上,林老师提到枚举最长路的边,然后断开,分别求子树的重心连接起来,更新答案
果然是NKU毕业的 .Orz

n那么小,我当时就否定了O(n)类的树dp
应该要想到 枚举 + dfs 这样子O(n^2)的复杂度!

用两个数组first[u],second[u]记录点u为根的子树的最长、次长的路
第一次dfs,任意根
第二次时,是调整整棵树的根的位置,然后通过递推计算出新根的first[],second[],更新答案

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<cstdlib>
#include<iostream>

using namespace std;

const int INF = 1000000000;
const int MAXN = 2510;

struct Edge
  {
int u, v, w;
Edge *next;
 Edge() {}
Edge(int _u , int _v , int _w)
 {
u = _u;
v = _v;
w = _w;
}
};

Edge *E[MAXN] , edges[MAXN*2] , *pE;

void add(int u , int v , int w)
  {
pE->u = u;
pE->v = v;
pE->w = w;
pE->next = E[u];
E[u] = pE++;
}

struct Pair
  {
int val , id;
};

Pair first[MAXN] , second[MAXN];

int longest , lid ,root;

void dfs1(int u ,int p)
  {
first[u].id = second[u].id = u;
first[u].val = second[u].val = 0;
for(Edge *it = E[u] ; it ; it = it->next)
 {
int v = it->v , w = it->w;
if(v == p)continue;
dfs1(v,u);
if( first[v].val + w >= first[u].val )// >=
 {
second[u] = first[u];
first[u].id = v;
first[u].val = first[v].val + w;
}
else if(first[v].val + w > second[u].val)
 {
second[u].id = v;
second[u].val = first[v].val + w;
}
}
if(longest < first[u].val + second[u].val)
 {
longest = first[u].val + second[u].val;
lid = u;
}
//printf("u %d %d %d %d %d\n",u,first[u].val , first[u].id , second[u].val , second[u].id);
}

void dfs2(int u ,int p , int preDist)//从上往下,更改根的位置,递推出新根的first[],second[]
  {
if( preDist != 0 )
 {
if(first[p].id != u)
 {
 second[u] = first[u];/**////////////////////记得别丢掉了
first[u].id = p;
first[u].val = preDist + first[p].val;
}
else
 {
if(second[p].val + preDist >= first[u].val)
 {
second[u] = first[u];
first[u].val = second[p].val + preDist;
first[u].id = p;
}
else if(second[p].val + preDist >= second[u].val)
 {
second[u].val = second[p].val + preDist;
second[u].id = p;
}
}
}

if(longest > first[u].val)
 {
longest = first[u].val;
lid = u;
}
for(Edge *it = E[u] ; it ; it = it->next)
 {
int v = it->v , w = it->w;
if(v == p)continue;
dfs2(v,u,w);
}
}

int main()
  {

#ifdef ONLINE_JUDGE
#else
freopen("in", "r", stdin);
#endif

int T ,t = 1;
for(scanf("%d",&T) ; T-- ;)
 {
int n , u , v, w;
scanf("%d",&n);
pE = edges;
for(int i = 0 ; i < n; i++)
 {
E[i] = NULL;
}
for(int i = 1 ; i< n ; i++)
 {
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}

//longest route
longest = 0;
dfs1(0,0);

//printf("longest %d %d\n",longest,lid);

int ans = longest , pos = lid , next;
vector<Edge> VE;
while( (next = first[pos].id) != pos)
 {
VE.push_back( Edge( pos , next , first[pos].val - first[next].val ) );
pos = next;
}
pos = lid , next = second[lid].id;
if(pos != next)
 {
VE.push_back(Edge(pos , next ,second[pos].val - first[next].val ));
pos = next;
while( (next = first[pos].id) != pos)
 {
VE.push_back( Edge( pos , next , first[pos].val - first[next].val ) );
pos = next;
}
}

for(int i = 0 , size = VE.size() ; i < size ; i++)
 {
u = VE[i].u , v = VE[i].v , w = VE[i].w;

// printf("route %d %d %d\n",u,v,w);

int _ans = 0;

longest = 0;
dfs1(u,v);
_ans = max(_ans , longest);
longest = INF;
dfs2(u,v,0);
int rootA = lid;

longest = 0;
dfs1(v,u);
_ans = max(_ans , longest);
longest = INF;
root = v;
dfs2(v,u,0);
int rootB = lid;

_ans = max(_ans , first[rootA].val + first[rootB].val + w);

ans = min(ans , _ans);
}

printf("Case %d: %d\n",t++,ans);
}
return 0;
}


|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|