F. Roads in the Kingdom(樹形dp)

題意：

給一張n個點n條邊的無向帶權(quán)圖
定義不便利度為所有點對最短距離中的最大值
求出刪一條邊之后，保證圖還連通時不便利度的最小值

$n <= 2e5 $
\(w_i <= 1e9\)

思路:樹形dp

這個圖是一個環(huán)上掛著很多顆樹，首先把這個環(huán)處理出來，
刪邊只能在環(huán)上進行，所以可以先求出以環(huán)上每個點為根的樹的直徑和最大深度dep，
答案來源分為二種

• 樹內(nèi)部兩點最遠距離 -> 直徑 (樹形dp 或者 兩次bfs)
• 兩棵樹深度最大的兩點配對

假設(shè)環(huán)長度為\(k\),把環(huán)變成一個序列\(a_1,a_2,...,a_k\) 令\(a_0 = a_k\)
選擇\(a_0\)做起點，用\(s_i\)表示第\(i\)個點到起點的距離

考慮每次斷開的邊為\(e(a_{i-1},a_i)\),那么答案分為三種情況

• 序列\(1\)到\(i-1\)中選兩個點配對取最大值
• 序列\(i\)到\(k\)中選兩個點配對取最大值
• 前后各取一個點配對取最大值

計算第一種情況
假設(shè)取的兩個點為\(1<=x<y<=i-1\),
則距離\(d = dep[x] + dep[y] + dis[x][y] = dep[x] - s[x] + dep[y] + s[y]\)
這樣我們只需要順序枚舉維護\(dep[x] - s[x]\)的最大值即可
同理，第二種情況只需要逆序枚舉維護\(dep[x] + s[x]\)的最大值即可

考慮第三種情況 假設(shè)取的點為\(1 <= x <= i - 1 , i <= y <= k\)
則距離\(d = dep[x] + dep[y] + dis[x][y] = dep[x] + dep[y] + s[k] - (s[y] - s[x])\)
$d = (dep[x] + s[k] + s[x]) + (dep[y] - s[y]) $
同理，順序可算出第一部分最大值，逆序可以算出第二部分最大值

最后在刪邊后三種情況的最大值里取最小值再和樹內(nèi)部直徑比較即可

#include<bits/stdc++.h> #define LL long long #define P pair<int,int> #define ls(i) seg[i].lc #define rs(i) seg[i].rc using namespace std; const int N = 2e5 + 10; const LL inf = 1e18; int read(){int x = 0;char c = getchar();while(c < '0' || c > '9') c = getchar();while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();return x; } vector<P>G[N]; int n,k; int a[N],pa[N],e[N]; LL s[N],dep[N],ans; void dfs(int u,int fa){pa[u] = fa;for(auto v:G[u]){if(v.first == fa) continue;if(pa[v.first] == 0) {e[v.first] = v.second;dfs(v.first,u);}else if(!k){int x = u;a[0] = v.first,s[1] = v.second;while(x != v.first) {a[++k] = x,s[k+1] = s[k] + e[x],x = pa[x];}a[++k] = v.first;}} } void dp(int u){pa[u] = 0;for(auto v:G[u]){if(pa[v.first] != 0){dp(v.first);ans = max(ans,dep[v.first] + v.second + dep[u]);dep[u] = max(dep[u], dep[v.first] + v.second);}} } LL sL[N],sR[N],L[N],R[N];///把環(huán)變成序列，斷開的邊左邊配對，右邊配對，左右配對的最大值 int main(){int u,v,w;n = read();for(int i = 1;i <= n;i++){u = read(),v = read(),w = read();G[u].push_back(P(v,w));G[v].push_back(P(u,w));}k = 0;ans = 0;dfs(1,-1);for(int i = 1;i <= k;i++) pa[a[i]] = 0;for(int i = 1;i <= k;i++) dp(a[i]);LL mx = -inf;L[0] = sL[0] = -inf;for(int i = 1;i <= k;i++){sL[i] = max(sL[i-1],dep[a[i]] + s[i] + mx);L[i] = max(L[i-1],dep[a[i]] + s[k] + s[i]);mx = max(mx, dep[a[i]] - s[i]);}sR[k+1] = R[k+1] = mx = -inf;for(int i = k;i >= 1;i--){sR[i] = max(sR[i+1],dep[a[i]] - s[i] + mx);R[i] = max(R[i+1],dep[a[i]] - s[i]);mx = max(mx, dep[a[i]] + s[i]);}LL tmp = inf;for(int i = 1;i <= k;i++) tmp = min(tmp,max(L[i-1]+R[i],max(sL[i-1],sR[i])));cout<<max(ans,tmp)<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/jiachinzhao/p/7305578.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 835 F Roads in the Kingdom(树形dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。