B-哇哇哇哇哇_一起来做题~欢乐赛7

题目描述

给你一棵n个节点的无根树，树的每条边都有流量限制，只有叶子节点能输出流量（如果某个叶子节点为根节点了那么就不输出流量），任意选定一个点为根节点，问流到根节点的最大流量是多少

样例

算法1

(换根dp)

分析

首先先考虑有根的情况，我们任选一个节点为跟节点
我们需要注意叶子节点的情况
叶子节点可以看成是无限流量但是有边的限制所以我们统计叶子节点的贡献的时候直接统计连向它的边的容量即可
定义 $f[u]$ 为以u为根的子树流向u节点的最大流量
很明显状态转移方程就为 $f[u] = \sum min(w[<u,j>],(j==叶子节点)?w[<u,j>]:f[j])$ $(w为流量限制)$
有了这个我们再考虑无根的情况
根据换根dp的思想
我们考虑根从一个节点转移到相邻节点对答案的影响
假设从节点u移动到节点v
我们先将 $f[u]$ 中<u,v>的贡献排除掉,用 $f'[u]$ 表示
$f'[u] = f[u] - f[v]$
则以v为根的答案(用 $f'[v]$ 表示)为, $f'[v] = min(f'[u],w[<u,v>]) + f[v]$
最终答案就是 $min(f[u],\{f'[v],...\})$ ( $f[u]$ 为最初的那个根节点)

状态转移方程：

if(!st[j]) f[u] += w[i];
else f[u] += min(w[i],f[j]);

//st[j] == false表示节点j是根节点

换根：

LL tmp;
if(!st[j]) tmp = f[u] - w[i];
else tmp = f[u] - min(w[i],f[j]);//排除节点j的影响

f[j] += min(w[i],tmp);//更新答案

时间复杂度 $O(n)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 1000010,mod = 998244353;
int h[N],ne[N * 2],e[N * 2],idx;
LL w[N * 2];
LL f[N];
bool st[N];
LL ans;
int n;

void add(int a,int b,LL c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void dfs1(int u,int father)
{
    f[u] = 0;
    st[u] = false;
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        st[u] = true;
        dfs1(j,u);
        if(!st[j]) f[u] += w[i];
        else f[u] += min(w[i],f[j]);
    }
}

void dfs2(int u,int father)
{
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        LL tmp;
        if(!st[j]) tmp = f[u] - w[i];
        else tmp = f[u] - min(w[i],f[j]);
        f[j] += min(w[i],tmp);
        dfs2(j,u);
    }
    ans = max(ans,f[u]);
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) h[i] = -1;
    idx = 0;
    ans = 0;
    for(int i = 1;i < n;i ++)
    {
        int a,b;
        LL c;
        scanf("%d%d%lld",&a,&b,&c);
        add(a,b,c); 
        add(b,a,c);
    }
    dfs1(1,0);
    dfs2(1,0);
    printf("%lld\n",ans);
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}