关于数据范围

P3376 【模板】网络最大流

Kobe303 @ 2021-08-30 20:07:12

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register 
#define il inline
const int inf = 1 << 28;
const int N = 205, M = 10005;
int head[N], ver[M], wei[M], nxt[M], d[N], now[M];
int n, m, s, t, cnt = 1;
ll maxflow;
queue<int> q;
void add(int x, int y, int z) {
    ver[++cnt] = y, wei[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
}

bool bfs() {
    memset(d, 0, sizeof(d));
    while (q.size()) q.pop();
    q.push(s); d[s] = 1; now[s] = head[s];
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i])
            if (wei[i] && !d[ver[i]]) {
                q.push(ver[i]);
                now[ver[i]] = head[ver[i]];
                d[ver[i]] = d[x] + 1;
                if (ver[i] == t) return 1;
            }
    }
    return 0;
}

int dinic(int x, int flow) {
    if (x == t) return flow;
    int rest = flow, k, i;
    for (i = now[x]; i && rest; i = nxt[i])
        if (wei[i] && d[ver[i]] == d[x] + 1) {
            k = dinic(ver[i], min(rest, wei[i]));
            if (!k) d[ver[i]] = 0;
            wei[i] -= k;
            wei[i ^ 1] + k;
            rest -= k;
        }
    now[x] = i;
    return flow - rest;
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d", &s, &t);
    for (int i = 1; i <= m; ++i) {
        int x, y, c; scanf("%d%d%d", &x, &y, &c);
        add(x, y, c), add(y, x, 0);
    }
    int flow = 0;
    while (bfs())
        while (flow = dinic(s, inf)) maxflow += flow;
    printf("%lld", maxflow);
    return 0;
}

这里我的 inf 取到 2^{28} 都可以过

然而 w 的极限能到 2^{31}-1,所以是数据较弱吗?


by Kobe303 @ 2021-08-30 20:09:00

Update:

我现在发现 inf2^{20} 都能过


by Kobe303 @ 2021-08-30 20:10:56

Update:

我现在发现 inf 越大跑得越快

网络流萌新,求教


by Bowen123 @ 2021-08-30 20:12:19

@Kobe303 inf是你的限定流量

就是每次增广所能跑的最大流量

如果限定的少的话固然增广次数就多

然后可能数据确实水


by Bowen123 @ 2021-08-30 20:13:01

我也才发现我的inf也才2*10^9


by KAMIYA_KINA @ 2021-08-30 20:21:55

Dinic 的实质就是你每次给一个流量让它进去跑,如果你每次给的流量足够大,能撑满一开始的水管,自然是最好的,不够大的话无非就是多跑几遍。


by Kobe303 @ 2021-08-30 20:23:25

@KAMIYA_KINA

谢谢啦,刚学网络流,可能会有一些比较无脑的问题


by Kobe303 @ 2021-08-30 20:23:52

@Bowen123

谢谢啦


|