已 AC,求助为啥我的 dinic 跑的这么慢

P3376 【模板】网络最大流

Engulf @ 2022-08-01 21:42:12

rt,如果是数据改过说下

看到 EK 跑的都比我这个快,很是不解。

明早来看。

836ms

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 205, M = 5005;
int n, m, s, t, maxflow;
int dep[N], flow[M << 1];
struct edge
{
    int to, nxt;
}e[M << 1];
int head[N], idx = 1;
void add(int x, int y, int w) {e[ ++ idx] = {y, head[x]}, head[x] = idx, flow[idx] = w;}

bool bfs()
{
    queue<int> q;
    memset(dep, 0, sizeof dep);
    q.push(s), dep[s] = 1;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (flow[i] && !dep[v])
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[t];
}
int dfs(int u, int in)
{
    if (u == t) return in;
    int out = 0;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (flow[i] && dep[v] == dep[u] + 1)
        {
            int fl = dfs(v, min(flow[i], in));
            flow[i] -= fl, flow[i ^ 1] += fl;
            in -= fl, out += fl;
        }
    }
    if (!out) dep[u] = 0;
    return out;
}

signed main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    for (int i = 1, x, y, w; i <= m; i ++ )
        scanf("%lld%lld%lld", &x, &y, &w), add(x, y, w), add(y, x, 0);
    while (bfs()) maxflow += dfs(s, 1e18);
    printf("%lld\n", maxflow);
    return 0;
}

by 8atemak1r @ 2022-08-01 21:49:18

@TMJYH09 你 dfs 的 for 循环条件里要加上 in 不为 0


by EastSnowLotus @ 2022-08-01 21:49:34

dinic 要算若干 bfs 和 dfs,应该会比较慢吧?

要是比其他 ACer 的也慢那才是代码有问题


by 8atemak1r @ 2022-08-01 21:49:39

不然你减来减去的没有意义啊


by 8atemak1r @ 2022-08-01 21:50:08

@CoCo_Candy 比我慢了快十倍(没记错的话


by EastSnowLotus @ 2022-08-01 21:50:11

@8atemak1r -0 珂海星


by 8atemak1r @ 2022-08-01 21:50:39

@CoCo_Candy 啥 -0


by 方123456 @ 2022-08-01 21:53:17

加了点小剪枝,类似搜不出来就不搜


by EastSnowLotus @ 2022-08-01 21:53:51

@8atemak1r

不然你减来减去的没有意义啊

减一堆 0 属于是(


by 方123456 @ 2022-08-01 21:54:41

加当前弧优化更快。


by jijidawang @ 2022-08-01 21:58:54

你们都在说啥,核心问题不是在于没加当前弧优化吗


| 下一页