dfs寻找增广路TLE

P3376 【模板】网络最大流

Njaso @ 2023-12-15 14:20:14

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

#ifdef LOCAL
#include "d:/coding/debug.h"
#else
#define debug(...) 114514
#endif

const int N = 205;
const int M = 1e4 + 5;
int n, m, s, t, cnt, tot;
int head[N], pre_e[N], dis[N], tag[N][N];
bool vis[N], flag;
struct Edge {
    int to, cost, nex;
} e[M];

void add_edge(int u, int v, int w) {
    e[cnt].to = v;
    e[cnt].cost = w;
    e[cnt].nex = head[u];
    head[u] = cnt;
    tag[u][v] = cnt;
    cnt++;
}

void find_augmenting_path(int u) {
    for (int i = head[u]; i != -1; i = e[i].nex) {
        int v = e[i].to, w = e[i].cost;
        if (w == 0 || vis[v]) continue;
        vis[v] = 1;
        pre_e[v] = i;
        dis[v] = min(dis[u], w);
        // debug(u, v, w, dis[v]);
        if (v == t) {
            cerr << "hi\n";
            // debug(u, v, dis[u], w, dis[t]);
            flag = 1;
            return;
        }
        find_augmenting_path(v);
        if (flag) return;
        vis[v] = 0;
    }
}

int temp_cnt;

void update() {
    // assert(0);
    temp_cnt++;
    debug(temp_cnt);
    int now = t;
    while (now != s) {
        int temp = pre_e[now];
        e[temp].cost -= dis[t];
        // debug(dis[t]);
        e[temp ^ 1].cost += dis[t];
        now = e[temp ^ 1].to;
    }
    tot += dis[t];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(head, -1, sizeof head);
    memset(tag, -1, sizeof tag);
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (tag[u][v] != -1) {
            int temp = tag[u][v];
            e[temp].cost += w;
        } else {
            add_edge(u, v, w);
            add_edge(v, u, 0);
        }
    }
    while (1) {
        memset(vis, 0, sizeof vis);
        memset(dis, 0x3f, sizeof dis);
        vis[s] = 1;
        // dis[s] = 0;
        flag = 0;
        find_augmenting_path(s);
        if (!flag) {
            // cerr << "hi\n";
            break;
        } else {
            update();
        }
    }
    cout << tot << '\n';
    return 0;
}

为什么用dfs寻找增广路会在某个地方卡很久 改成用bfs后就过了


by toolazy @ 2024-01-06 13:26:00

是这样子的,纯的 FF 是肯定会被卡的

比如这个例子,是典中典的 FF-killer

4 5 1 4
1 2 114514
2 4 114514
1 3 114514
3 4 114514
2 3 1

你可以自己上 Graph Editor 上看看这张图,直接把后面5行复制粘贴上去就好了(别忘了开 Directed

那么在这个例子当中,如果运气不好(这里就不细究什么邻接表、前向星区别之类的了),第一次选择了 1-2-3-4 这条路增广(流量贡献 +1,边 2-3 满流,残留网络边 3-2 更新),然后第二次又选择了 1-3-2-4 这条路来增广(流量贡献 +1,边 3-2 满流,对应的反向边 2-3 更新)之后,图就变成了这样:

1 2 114513
2 4 114513
1 3 114513
3 4 114513
2 3 1

十分可悲的,由于中间那条 2-3 边的存在让我们做了很多很多很多很多の无用功,也就是说我们需要增广整整 2\times114514=229028 次!

问题就在这里:我们明明可以直接两次增广 1-2-41-3-4,却偏偏选择了更长的 1-2-3-41-3-2-4,那我们能不能只用 BFS 来找最短的路来增广呢?

这就是 EK 算法,也就是你说的 改成用bfs后就过了 的原因。


by Njaso @ 2024-01-20 20:06:17

@_venti 学到了,感谢


|