图论--网络流--最大流洛谷P4722（hlpp）

题目描述

给定 nn 个点，mm 条有向边，给定每条边的容量，求从点 ss 到点 tt 的最大流。

输入格式

第一行包含四个正整数nn、mm、ss、tt，用空格分隔，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来mm行每行包含三个正整数u_iui、v_ivi、c_ici，用空格分隔，表示第ii条有向边从u_iui出发，到达v_ivi，容量为c_ici

输出格式

一个整数，表示ss到tt的最大流

输入输出样例

输入 #1

输出 #1

输入 #2

10 16 1 2

1 3 2

1 4 2

5 2 2

6 2 2

3 5 1

3 6 1

4 5 1

4 6 1

1 7 2147483647

9 2 2147483647

7 8 2147483647

10 9 2147483647

8 5 2

8 6 2

3 10 2

4 10 2

输出 #2

//500ms 秒掉洛谷推流问题

#include <algorithm>

#include <iostream>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

typedef long long LL;

typedef long long F_type;

const int MAXN = 1.2e3 + 10, INF = 0x3f3f3f3f;

const LL LINF = (LL)INF << 32 | INF;

struct Edge

{

    int v, rev;

    F_type cap;

    Edge(int a, F_type b, int c) : v(a), rev(c), cap(b) {}

};

const F_type maxf=LINF;

F_type exflow[MAXN];

int h[MAXN], cnt[MAXN];

int ht, N, S, T, labelcnt;

vector<Edge> G[MAXN];

vector<int> hq[MAXN];

void clear(int n = MAXN - 1)

{

    ht = labelcnt = 0;

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

        G[i].clear();

}

void addEdge(int u, int v, F_type cap)

{

    G[u].emplace_back(v, cap, G[v].size());

    G[v].emplace_back(u, 0, G[u].size() - 1);

}

void update(int u, int newh)

{

    ++labelcnt;

    if (h[u] != N + 1)

        --cnt[h[u]];

    h[u] = newh;

    if (newh == N + 1)

        return;

    ++cnt[ht = newh];

    if (exflow[u] > 0)

        hq[newh].push_back(u);

}

void globalRelabel()

{

    queue<int> q;

    for (int i = 0; i <= N + 1; i++)

        hq[i].clear();

    for (int i = 0; i <= N; i++)

        h[i] = N + 1, cnt[i] = 0;

    q.push(T);

    labelcnt = ht = h[T] = 0;

    while (!q.empty())

    {

        int u = q.front();

        q.pop();

        for (Edge& e : G[u])

        {

            if (h[e.v] == N + 1 && G[e.v][e.rev].cap)

            {

                update(e.v, h[u] + 1);

                q.push(e.v);

            }

        }

        ht = h[u];

    }

}

void push(int u, Edge& e)

{

    if (exflow[e.v] == 0)

        hq[h[e.v]].push_back(e.v);

    F_type df = min(exflow[u], e.cap);

    e.cap -= df;

    G[e.v][e.rev].cap += df;

    exflow[u] -= df;

    exflow[e.v] += df;

}

void discharge(int u)

{

    int nxth = N + 1;

    for (Edge& e : G[u])

        if (e.cap)

        {

            if (h[u] == h[e.v] + 1)

            {

                push(u, e);

                if (exflow[u] <= 0)

                    return;

            }

            else

                nxth = min(nxth, h[e.v] + 1);

        }

    if (cnt[h[u]] > 1)

        update(u, nxth);

    else

        for (; ht >= h[u]; hq[ht--].clear())

        {

            for (int& j : hq[ht])

                update(j, N + 1);

        }

}

F_type maxFlow(int s, int t, int n)

{

    S = s, T = t, N = n;

    memset(exflow, 0, sizeof(exflow));

    exflow[S] = maxf;

    exflow[T] = -maxf;

    globalRelabel();

    for (Edge& e : G[S])

        push(S, e);

    for (; ht >= 0; --ht)

    {

        while (!hq[ht].empty())

        {

            int u = hq[ht].back();

            hq[ht].pop_back();

            discharge(u);

            if (labelcnt > (N << 2))

                globalRelabel();

        }

    }

    return exflow[T] + maxf;

}

int main()

{

    int n, m, s, t, u, v, w;

    scanf("%d%d%d%d", &n, &m, &s, &t);

    while (m--)

    {

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

        addEdge(u, v, w);

    }

    printf("%d", maxFlow(s, t, n));

    return 0;

}

巴特西

图论--网络流--最大流洛谷P4722（hlpp）

题目描述

输入格式

输出格式

输入输出样例

最新文章

热门文章

巴特西

图论--网络流--最大流 洛谷P4722（hlpp）

题目描述

输入格式

输出格式

输入输出样例

最新文章

热门文章

图论--网络流--最大流洛谷P4722（hlpp）