链接:

https://www.acwing.com/problem/content/289/

题意:

有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。

我们可以把交叉点看作树中的节点，编号为 1~N，河道则看作树中的无向边。

每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。

河道中单位时间流过的水量不能超过河道的容量。

有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。

除了源点之外，树中所有度数为 1 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。

也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。

在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。

除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。

整个水系的流量就定义为源点单位时间发出的水量。

在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。

思路:

建树, 第一遍DFS跑以1为根, 即以1为源点的最大流量.
第二遍不断换根去求.
对于个点, 其父节点已经计算完毕, 推出式子,先算出除当前节点外所有节点到根节点的流量.
再将其累积到当前节点.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e5+10;

const int INF = 1e9;

vector<pair<int, LL> > G[MAXN];

LL Dp1[MAXN], Dp2[MAXN];

int n;

LL Dfs1(int u, int fa)

{

    LL flow = 0;

    for (int i = 0;i < G[u].size();i++)

    {

        int node = G[u][i].first;

        LL maxflow = G[u][i].second;

        if (node == fa)

            continue;

        LL tmp = Dfs1(node, u);

        flow += min(tmp, maxflow);

    }

    if (flow == 0)

    {

        Dp1[u] = INF;

        return INF;

    }

    else

    {

        Dp1[u] = flow;

        return flow;

    }

}

LL Dfs2(int u, int fa)

{

    for (int i = 0;i < G[u].size();i++)

    {

        int node = G[u][i].first;

        LL maxflow = G[u][i].second;

        if (node == fa)

            continue;

        if (Dp1[node] == INF)

        {

            Dp2[node] = maxflow;

        }

        else

        {

            LL tmp = Dp2[u]-min(Dp1[node], maxflow);

            Dp2[node] = Dp1[node] + min(maxflow, tmp);

        }

        Dfs2(node, u);

    }

}

int main()

{

    int t;

    scanf("%d", &t);

    int u, v, w;

    while (t--)

    {

        memset(Dp1, 0, sizeof(Dp1));

        memset(Dp2, 0, sizeof(Dp2));

        scanf("%d", &n);

        for (int i = 1;i <= n;i++)

            G[i].clear();

        for (int i = 1;i < n;i++)

        {

            scanf("%d%d%d", &u, &v, &w);

            G[u].push_back(make_pair(v, w));

            G[v].push_back(make_pair(u, w));

        }

        Dfs1(1, 0);

        Dp2[1] = Dp1[1];

        Dfs2(1, 0);

        LL res = 0;

        for (int i = 1;i <= n;i++)

            res = max(res, Dp2[i]);

//        for (int i = 1;i <= n;i++)

//            cout << Dp2[i] << ' ' ;

//        cout << endl;

        printf("%lld\n", res);

    }

    return 0;

}

巴特西

Acwing-287-积蓄程度(树上DP, 换根)

链接:

题意:

思路:

代码:

最新文章

热门文章