題目描述

有一個樹形的水系，由 N-1 條河道和 N 個交叉點組成。

我們可以把交叉點看作樹中的節點，編號為 1~N，河道則看作樹中的無向邊。

每條河道都有一個容量，連接 x 與 y 的河道的容量記為 c(x,y)。

河道中單位時間流過的水量不能超過河道的容量。

有一個節點是整個水系的發源地，可以源源不斷地流出水，我們稱之為源點。

除了源點之外，樹中所有度數為 1 的節點都是入海口，可以吸收無限多的水，我們稱之為匯點。

也就是說，水系中的水從源點出發，沿著每條河道，最終流向各個匯點。

在整個水系穩定時，每條河道中的水都以單位時間固定的水量流向固定的方向。

除源點和匯點之外，其余各點不貯存水，也就是流入該點的河道水量之和等于從該點流出的河道水量之和。

整個水系的流量就定義為源點單位時間發出的水量。

在流量不超過河道容量的前提下，求哪個點作為源點時，整個水系的流量最大，輸出這個最大值。

$O(N^2)$解法

加入這是一棵有根樹，我們可以直接利用樹形DP來進行求解。

設$g[i]$表示以$i$為根的子樹中，以$i$為源點時的最大流量。

若當前根節點為$root$，子樹的根節點為$son$。

• 當$size(son)=1$時，有且僅有一條河道，可以直接累加權值。
• 當$size(son)>1$時，我們需要將$g[son]$和邊權$v$進行比較，顯然兩者取最小值即可。

狀態轉移方程就是：
$$g[root]=\sum _{son\in son(root)}\{\begin{array}{r}v(root,son),size(son)=1\\ min(g[son],v),size(son)>1\end{array}$$

每一個點按照上述方法做一遍樹形DP，時間復雜度：$O(n^2)$

$O(n)$解法

由于這是一棵無根樹，不同的根會產生不同的答案，故我們可以思考一下如何進行換根。

換根的主要思路就是如何處理根與根的轉化。

設$f[i]$表示以$i$為根的子樹中，答案的最大值。

顯然，對于$i$到$j$的轉移，可以這么考慮：

• 不變的答案為：在以$1$為根的樹中，以$j$為根的子樹的答案。即$g[y].$
• 變化的答案為：$j$上面的答案要變成以j為根的答案。即以$i$為根的總答案減去在原子樹中，以$j$為根的總答案，在不考慮路徑限制的情況下，即為j上面的答案；再與$v(i,j)$取最小值即可。我們現在考慮如何求出前者：以$i$為根的總答案為$f[i]$,以j為根的答案為$min(v(i,j),g[j])$.現在轉移方程就一目了然了。
• 對于單獨的點，直接以邊權為答案即可。

有狀態轉移方程：
$$f[i]=\{\begin{array}{r}v(i,j),size(j)=1\\ g[j]+min(v(i,j),f[i]?min(g[j],v(i,j))),size(j)>1\end{array}$$

代碼如下：

#include <bits/stdc++.h>using namespace std; const int N = 200005;int n, ans, tot; int in[N], f[N], g[N], Link[N]; struct edge { int y,v,next; } e[N*2];inline int read(void) {int s = 0, w = 1; char c = getchar();while (c < '0' || c > '9') c = getchar();while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();return s * w; } void clear(void) {ans = 0, tot = 0;memset(in,0,sizeof in);memset(Link,0,sizeof Link);return; }void add(int x,int y,int v) {tot ++;e[tot] = edge{y,v,Link[x]};Link[x] = tot;return; }void dfs(int x,int fa) {g[x] = 0;for (int i=Link[x];i;i=e[i].next){int y = e[i].y;int v = e[i].v; if (y == fa) continue;dfs(y,x);if (in[y] == 1) g[x] += v;else g[x] += min(g[y],v);//判斷流量是否會超出當前容量 }return; }void dp(int x,int fa) {for (int i=Link[x];i;i=e[i].next) {int y = e[i].y;int v = e[i].v;if (y == fa) continue;if (in[x] > 1) f[y] = g[y]+min(f[x]-min(g[y],v),v);if (in[x] == 1) f[y] = g[y]+v;dp(y,x);}return; }void work(void) {clear();n = read();for (int i=1;i<n;++i){int x = read(), y = read(), v = read();add(x,y,v), add(y,x,v);in[x] ++, in[y] ++;}dfs(1,0), f[1] = g[1], dp(1,0);for (int i=1;i<=n;++i) ans = max(ans,f[i]);printf("%d\n", ans);return; }int main(void) {freopen("degree.in","r",stdin);freopen("degree.out","w",stdout);int T = read();while (T --) work();return 0; }

總結

以上是生活随笔為你收集整理的『树形DP·换根法』Accumulation Degree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。