Rockdu's Blog

题目描述

如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。

输入输出格式

输入格式：

第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）

输出格式：

一行，包含一个正整数，即为该网络的最大流。

输入输出样例

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

50

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=25

对于70%的数据：N<=200，M<=1000

对于100%的数据：N<=10000，M<=100000

题目中存在3条路径：

4-->2-->3，该路线可通过20的流量

4-->3，可通过20的流量

4-->2-->1-->3，可通过10的流量（边4-->2之前已经耗费了20的流量）

故流量总计20+20+10=50。输出50。

垃圾洛谷，花了一个下午学的预流推进跑的比Dinic还慢。我就不贴Dinic了，这里放一个预流推进：

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1e4 + 5;
const int maxm = 1e5 + 5;
struct edge {
    int v, w, next;
}e[maxm << 1];
int head[maxn], cnt, n, m, s, t;
void adde(const int &u, const int &v, const int &w) {
    e[++cnt] = (edge) {v, w, head[u]}, head[u] = cnt;
    e[++cnt] = (edge) {u, 0, head[v]}, head[v] = cnt;
}
struct node {
    int x, h;
    node(int rx, int rh) {x = rx, h = rh;}
    bool operator <(const node &a) const {return h < a.h;}
};
namespace HLPP {
    const int inf = 0x3f3f3f3f;
    int pool[maxn], gap[maxn], h[maxn], N;
    priority_queue<node > q;
    int pushflow(int x, int y, int i) {
        int w = min(e[i].w, pool[x]);
        pool[x] -= w, pool[y] += w, e[i].w -= w, e[i ^ 1].w += w;
        return w;
    }
    void Sign(int mn, int s, int t) {
        for(register int i = 1; i <= N; ++i)
            if(h[i] > mn && i != s && i != t) h[i] = N + 1;
    }
    int maxflow(int n, int s, int t) {
        pool[s] = inf, N = h[s] = n, q.push(node(s, n));
        while(!q.empty()) {
            int u = q.top().x, v;
            q.pop();
            if(!pool[u]) continue;
            for(register int i = head[u]; i; i = e[i].next) {
                v = e[i].v;
                if((u == s || h[u] == h[v] + 1) && pushflow(u, v, i))
                    if(v != s && v != t) q.push(node(v, h[v]));
            }
            if(pool[u] && u != s && u != t) {
                if(!(--gap[h[u]])) Sign(h[u], s, t);
                ++gap[++h[u]], q.push(node(u, h[u]));
            }
        }
        return pool[t];
    }
}

int main() {
    int a, b, c;
    scanf("%d%d%d%d", &n, &m, &s, &t), cnt = 1;
    for(register int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        adde(a, b, c);
    }
    printf("%d", HLPP::maxflow(n, s, t));
    return 0;
}