BZOJ4890 [Tjoi2017]城市【树形dp】-白红宇

BZOJ4890 [Tjoi2017]城市【树形dp】

阅读量：5024 次

发布时间：2019-06-12

本文共 2720 字，大约阅读时间需要 9 分钟。

题目链接

题解

枚举断开哪一条边，然后对剩余的两棵树分别做一遍换根法树形dp

需要求出每个点到树中其它点距离的最大值\(f[i]\)和次大值\(g[i]\)【用以辅助换根计算最大值】

求出每棵树中的最长路径，然后再将两棵树中\(f[i]\)最小值相连保证相连后产生的最大值最小

\(O(n^2)\)的复杂度

如果怕被卡常，可以知道要切的边一定在直径上，虽然上界没有变，但速度可以快不少

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
          
           (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
           
            #define LL long long intusing namespace std;const int maxn = 5005,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int h[maxn],ne = 1;struct EDGE{int from,to,nxt,w,flag;}ed[maxn << 1];inline void build(int u,int v,int w){ ed[++ne] = (EDGE){u,v,h[u],w,1}; h[u] = ne; ed[++ne] = (EDGE){v,u,h[v],w,1}; h[v] = ne;}int f[maxn],g[maxn],ch[maxn],d[maxn],du,path[maxn],fa[maxn];int n,ans,fans,mnans;void DFS(int u,int Fa){ if (d[u] > d[du]) du = u; Redge(u) if ((to = ed[k].to) != Fa){ d[to] = d[u] + ed[k].w; path[to] = k; DFS(to,u); }}void dfs(int u){ f[u] = g[u] = 0; Redge(u) if (ed[k].flag && (to = ed[k].to) != fa[u]){ fa[to] = u; d[to] = ed[k].w; dfs(to); if (f[to] + ed[k].w > f[u]){ g[u] = f[u]; f[u] = f[to] + ed[k].w; ch[u] = to; } else if (f[to] + ed[k].w > g[u]) g[u] = f[to] + ed[k].w; } fans = max(fans,f[u]);}void dfs2(int u){ if (fa[u]){ int v = fa[u]; if (ch[v] == u){ if (g[v] + d[u] > f[u]){ g[u] = f[u]; f[u] = g[v] + d[u]; ch[u] = v; } else if (g[v] + d[u] > g[u]) g[u] = g[v] + d[u]; } else { if (f[v] + d[u] > f[u]){ g[u] = f[u]; f[u] = f[v] + d[u]; ch[u] = v; } else if (f[v] + d[u] > g[u]) g[u] = f[v] + d[u]; } } Redge(u) if (ed[k].flag && (to = ed[k].to) != fa[u]){ dfs2(to); } fans = max(fans,f[u]); mnans = min(mnans,f[u]);}int dp(int rt){ d[rt] = 0; fa[rt] = 0; dfs(rt); mnans = INF; dfs2(rt); return mnans;}int main(){ n = read(); int a,b,w; ans = INF; for (int i = 1; i < n; i++){ a = read(); b = read(); w = read(); build(a,b,w); } d[du = 1] = 0; DFS(1,0); path[du] = 0; d[du] = 0; DFS(du,0); int t1,t2; for (int i = du; path[i]; i = ed[path[i]].from){ int k = path[i]; ed[k].flag = ed[k ^ 1].flag = false; cls(f); cls(g); fans = 0; t1 = dp(ed[k].from); t2 = dp(ed[k].to); //REP(j,n) printf("%d ",f[j]); puts(""); fans = max(fans,t1 + t2 + ed[k].w); //printf("(%d,%d) mx = %d\n",ed[k].to,ed[k].from,fans); ans = min(ans,fans); ed[k].flag = ed[k ^ 1].flag = true; } printf("%d\n",ans); return 0;}