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
这条路增广(流量贡献 2-3
满流,残留网络边 3-2
更新),然后第二次又选择了 1-3-2-4
这条路来增广(流量贡献 3-2
满流,对应的反向边 2-3
更新)之后,图就变成了这样:
1 2 114513
2 4 114513
1 3 114513
3 4 114513
2 3 1
十分可悲的,由于中间那条 2-3
边的存在让我们做了很多很多很多很多の无用功,也就是说我们需要增广整整
问题就在这里:我们明明可以直接两次增广 1-2-4
和 1-3-4
,却偏偏选择了更长的 1-2-3-4
和 1-3-2-4
,那我们能不能只用 BFS
来找最短的路来增广呢?
这就是 EK
算法,也就是你说的 改成用bfs后就过了
的原因。
by Njaso @ 2024-01-20 20:06:17
@_venti 学到了,感谢