问题描述

大意就是给了你一棵树,你可以选任意节点作为根节点。根节点为源点,所有叶子节点为汇点,求出最大流。

输入

第一行T,表示T组数据。
每组数据第一行为n (n<=200005),表示有n个节点,接下来n-1行描述每一条边的端点和流量,

输出

每一组数据输出一个数字,为该组数据的最大流量。

思路

暴力枚举每一个顶点作为源点的n^2做法应该不难想到。然后在《算法进阶指南》上学到了O(n)的高级操作(二次扫描与换根法)。

我们任选一个节点作为源点。先扫描一遍,处理从出每个节点出发流向子树的最大流量。然后再扫描一遍,可以处理出每个点作为源点的最大流。

第一遍扫描可以用一个简单的DP解决,第i个点的最大流量储存为f[i]。第二遍扫描时可以利用已经处理好的f数组,推出每个点的答案,第i个点的答案储存为g[i]。我们从根节点开始dfs,设当前节点为x,它的子节点为y,从x流向除y以外其余部分的流量可以表示为g[x]-min(f[y], flow(x, y)),所以g[y]=min(g[x]-min( f[y], flow(x, y)),flow(x, y) )+f[y]。

细节

  1. 当求f[i],和g[i]时,若i节点度数为1要注意特判!!!
  2. 式子中的变量不要弄混了。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 200005
using namespace std;

struct Edge {int next, to, flow;} edge[MAXN*2];

int T, n, x, y, z, ans, cnt, f[MAXN], g[MAXN], deg[MAXN], head[MAXN];

void addedge(int from, int to, int flow)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].flow=flow;
    deg[to]++;
    head[from]=cnt;
}

void init()
{
    memset(edge, 0, sizeof(edge));
    for(int i=1; i<MAXN; i++)
        f[i]=g[i]=head[i]=deg[i]=0;
    cnt=ans=0;
}

void dfs1(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs1(to, x);
        if(deg[to]==1) f[x]+=edge[i].flow;
        else f[x]+=min(f[to], edge[i].flow);
    }
}

void dfs2(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        if(deg[x]==1) g[to]=f[to]+edge[i].flow;
        else g[to]=f[to]+min(g[x]-min(f[to], edge[i].flow), edge[i].flow);
        dfs2(to, x);
    }
    ans=max(ans, g[x]);
}


int main()
{
    scanf("%d", &T);
    while(T--)
    {
        init();
        scanf("%d", &n);
        for(int i=1; i<n; i++)
        {
            scanf("%d%d%d", &x, &y, &z);
            addedge(x, y, z);
            addedge(y, x, z);
        }
        dfs1(1, 0);
        g[1]=f[1];
        dfs2(1, 0);
        printf("%d\n", ans);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注