Twiter_ln @ 2023-11-03 17:22:56
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 207;
typedef long long lli;
int n, m, S, T;
int x, y, z;
struct pot{
int v, nxt;
lli val;
}E[50*N];
int head[N], tot = 1;
inline void Add_edge(int u, int v, int val) {
E[++tot].v = v;
E[tot].val = val;
E[tot].nxt = head[u];
head[u] = tot;
}
int dep[N], cur[N];
inline bool bfs() {
queue <int> q;
q.push(S);
memset(dep, 0, sizeof(dep));
dep[S] = 1;
int u, v;
while(q.size()) {
u = q.front();
q.pop();
for(int i=head[u];i;i=E[i].nxt) {
v = E[i].v;
if(dep[v] || !E[i].val) continue;
dep[v] = dep[u] + 1;
q.push(v);
if(v == T) return true;
}
}
return false;
}
inline lli dfs(int u, lli nowflow) {
if(u == T) return nowflow;
if(nowflow == 0) return 0;
int v;
lli sum = 0, f;
for(int i=cur[u];i;i=E[i].nxt) {
v = E[i].v;
cur[u] = i;
if(dep[v] != dep[u]+1 || !E[i].val) continue;
f = dfs(v, min(E[i].val, nowflow));
E[i].val -= f;
E[i^1].val += f;
sum += f;
nowflow -= f;
}
return sum;
}
void Dinic() {
lli ans = 0;
while(bfs()) {
memcpy(cur, head, sizeof(cur));
ans += dfs(S, 0x3fffffffffffffff);
}
printf("%lld\n", ans);
}
int main() {
scanf("%d%d%d%d", &n, &m, &S, &T);
for(int i=1;i<=m;++i) {
scanf("%d%d%d", &x, &y, &z);
Add_edge(x, y, z);
Add_edge(y, x, 0);
}
Dinic();
return 0;
}
(无语子......)
by adam01 @ 2023-11-03 17:38:00
@Twiter_ln 你 bfs 的时候没有重置当前弧(cur 数组)。
by Mikefeng @ 2023-11-03 17:41:54
@adam01 你再想想
by adam01 @ 2023-11-03 17:43:14
@Mikefeng 没事了,我瞎了。
by Mikefeng @ 2023-11-03 17:43:56
应该是 dfs 里面没有 nowflow 为
by Twiter_ln @ 2023-11-03 18:51:09
@Mikefeng
if(nowflow == 0) return 0;
by reveal @ 2023-11-03 18:53:06
@Twiter_ln 不是,是
nowflow -= f;
后面需要立刻判断 nowflow==0
时退出。
否则这条弧可能因为流量不足而被跳过(但实际上还能继续推流),然后你就得到了一个常数巨大的 EK 算法。
by Twiter_ln @ 2023-11-03 18:55:32
@reveal
by reveal @ 2023-11-03 18:57:10
贴一个 rvalue 的原话:
因为如果你不理解Dinic的过程与复杂度分析, 你几乎一 定 会 写 假.
有些看起来很不起眼的小细节可能影响着整个算法的时间复杂度.
首先就是当前弧优化的跳出条件, 我为啥要把"除了最后一条边之外"那句话加粗呢? 因为你如果把跳出判定写在
for
循环里会慢10 倍以上, 根本不是常数问题, 是复杂度出了锅. 因为你会漏掉最后那个可能没跑满的弧, 而分层图 BFS 会在当前图没有被割断的时候一直跑跑跑, 于是就锅了.
by reveal @ 2023-11-03 18:58:26
@Twiter_ln 他是在 for 中判断了流量为 0 之后在更新当前弧的,但你完全没判,所以你这就是个常数巨大的 EK,连跑不满的机会都没有。
by Twiter_ln @ 2023-11-03 19:05:09
@reveal