【每日一题】Accumulation Degree

Solution

普通的树形dp。

首先设 $g[u]$ 为从点 $u$ 向 $u$ 的子树推流，所能达到的最大流量；

那么有：

$g[u] = \sum{f(u, v)}$

$f(u, v) = \begin{cases} cap_{u, v}, & \text{if $v$ is leaf} \\ min(cap_{u, v}, g[v]), & \text{else} \end{cases}$

其中 $v$ 为 $u$ 的孩子， $cap_{u, v}$ 为 $u$ 和 $v$ 之间的边的流量上限。

设 $dp[u]$ 为从 $u$ 向整棵树推流，所能达到的最大流量，那么有：

$dp[u] = \begin{cases} g[u], & \text{if $u$ is root} \\ g[u] + min(cap_{fa, u}, dp[fa] - f(fa, u)), & \text{else} \end{cases}$

作两遍dfs，分别求出 $g[i]$ 和 $dp[i]$ 的值，取 $max(dp[i])$ 输出即可，复杂度 $O(n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct edge {
  int v, cap;
};

vector<edge> G[200005];
ll dp[200005];

ll f(int v, int cap) {
  if ((int) G[v].size() == 1) {
    return cap;
  } else {
    return min<ll>(cap, dp[v]);
  }
}

void dfs(int u, int fa) {
  dp[u] = 0;
  for (auto e : G[u]) {
    if (e.v != fa) {
      dfs(e.v, u);
      dp[u] += f(e.v, e.cap);
    }
  }
}

void dfs(int u, int fa, int cap) {
  if (fa > 0) {
    dp[u] += min<ll>(cap, dp[fa] - f(u, cap));
  }
  for (auto e : G[u]) {
    if (e.v != fa) {
      dfs(e.v, u, e.cap);
    }
  }
}

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      G[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      G[x].push_back({ y, z });
      G[y].push_back({ x, z });
    }
    dfs(1, -1), dfs(1, -1, -1);
    ll res = *max_element(dp + 1, dp + 1 + n);
    cout << res << "\n";
  }
}