最大流最小割模板题。

想当年第一次打开 BZOJ 做完 A + B 之后看得一脸懵逼的就是这道题,没想到现如今看起来这么简单

不过还是没有秒切,双向边没看到调了好久 QAQ

好了,关于那个连边。这是本人单向边网络流连边:

1
2
3
4
5
inline void add_edge(int u, int v, int w) {
nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, val[tot] = 0, hed[v] = tot++;
return;
}

这是本人的双向网络流连边(连两遍也是一样的):

1
2
3
4
5
inline void add_edge(int u, int v, int w) {
nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, val[tot] = w, hed[v] = tot++;
return;
}

另外 $最大流 = 最小割$ 不必多说了吧,贴个直观的证明(来自:https://jecvay.com/2014/11/what-is-min-cut.html):

1.最大流不可能大于最小割, 因为最大流所有的水流都一定经过最小割那些割边, 流过的水流怎么可能比水管容量还大呢?

2.最大流不可能小于最小割, 如果小, 那么说明水管容量没有物尽其用, 可以继续加大水流.

那么 SAP + 当前弧优化 + 断层优化 + 反向 BFS 一遍轻松跑过。

去他妈的NOI难度

从 $S$ 到 byx 的每个人连条容量为生命的边,从手气君的每个人到 $E$ 连条容量为生命的边;如果 byx 的这个人能打赢对方的某个人连一条容量为 $1$ 的边,$+1s$ 的话直接加到生命里,最后跑一遍最大流即可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×