luogu3761 [TJOI2017]城市

重点是求树的直径、半径。

参考这里

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, uu[5005], vv[5005], ww[5005], cnt, hea[5005], zui[5005], cii[5005], dis;
//zui means the longest chain, cii means the second longest chain, all for length
int son[5005], ans=0x3f3f3f3f;
bool vis[5005];
struct Edge{
int too, nxt, val;
}edge[10005];
void add_edge(int fro, int too, int val){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
edge[cnt].val = val;
hea[fro] = cnt;
}
void getD(int x){
vis[x] = true;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(!vis[t]){
getD(t);
int tmpdis=zui[t]+edge[i].val;
if(tmpdis>zui[x]){
cii[x] = zui[x];
zui[x] = tmpdis;
son[x] = t;
}
else if(tmpdis>cii[x])cii[x] = tmpdis;
}
}
dis = max(dis, zui[x]+cii[x]);
}
void getR(int x, int fadis){
dis = min(dis, max(fadis, zui[x]));
vis[x] = false;
for(int i=hea[x]; i; i=edge[i].nxt){
int t=edge[i].too;
if(vis[t]){
if(t==son[x])getR(t, max(fadis+edge[i].val, edge[i].val+cii[x]));
elsegetR(t, max(fadis+edge[i].val, edge[i].val+zui[x]));
}
}
}
void clr(){
memset(zui, 0, sizeof(zui));
memset(cii, 0, sizeof(cii));
}
int main(){
cin>>n;
for(int i=1; i<n; i++){
scanf("%d %d %d", &uu[i], &vv[i], &ww[i]);
add_edge(uu[i], vv[i], ww[i]);
add_edge(vv[i], uu[i], ww[i]);
}
for(int i=1; i<n; i++){
clr();
int d1, d2, r1, r2;
vis[vv[i]] = true; getD(uu[i]); d1 = dis;
dis = 0; getD(vv[i]); d2 = dis;
dis = 0x3f3f3f3f;
vis[vv[i]] = false; getR(uu[i], 0); r1 = dis;
dis = 0x3f3f3f3f; getR(vv[i], 0); r2 = dis;
ans = min(ans, max(max(d1, d2), r1+r2+ww[i]));
}
cout<<ans<<endl;
return 0;
}