「CF1383F」Special Edges

你想了半天，用 dinic 加上一个很妙的优化做法还被卡常了，而 hlpp 裸写就直接过了，学谁不用我说了⑧

Description

给定一张 $n$ 个点图以及 $m$ 条边，每条边连接 $u$， $v$，流量为 $w$ 。其中还有 $k$ 条特出的边，流量会改变。共有 $q$ 次询问，每次给出 $k$ 条特出边的流量，求这张图 $1$ 到 $n$ 的最大流。

$2 \le n \le 10^4,1\le m \le 10^4,1 \le k \le \min(10,m)$

$1 \le q \le 2 \cdot 10^5,0 \le w \le 25$

Solution

首先有一个暴力做法，每次流一遍，但是这个做法没救了（hlpp，永远滴神！）。

我们考虑会修改的边很少，只有 $10$ 条，能不能把每次都流优化掉。

考虑这么一个子问题，假设 $k = 1$ ，也就是只有一条边会改变，有没有什么优秀的做法。虽然题目要求的是 $1$ 到 $n$ 的最大流，但是最大流和最小割其实是一回事，所以考虑如果只有一条边会改变的话，这条边对最小割的影响是什么。设这条边的流量为 $w$，如果这条边不在最小割里，那么我们无论把这条边的流量增加多少，对最终的割大小都没有影响。如果这条边在最小割里面，我们不妨先在图里把这条边删掉，求出剩下图中的最小割 $v$，那么 $v+w$ 和原图的最小割是一样的。考虑如何计算这个原图的最小割，我们先把这条边删掉跑一遍最小割，加上 $w$，求出这个值为 $\text{val1}$ ，然后我们在原图上加上这条边，将它的权值设成比 $w$ 大（或是等于 $w$）的任意值（不妨设为 $w+1$）再次跑一次最小割，值为 $\text{val2}$ 。我们发现 $\text{val1}$ 为包含这条边的最小割，而 $\text{val2}$ 在原图最小割不包含这条边的时候就是原图的最小割，否则严格不优于 $\text{val1}$，那么原图的最小割 $\text{val} = \min(\text{val1}, \text{val2})$ 。

既然 $1$ 条边可以做了，那么 $10$ 条边也就一样做了，无非就是加个状压，枚举一个 01 状态表示一条边不被加进图里或者加进图里后边权调大，每次加入一堆边进去。询问的时候就对每一种状态取个 $min$，最优解一定会在最小割中要割掉的边没加入的图中并且加入图中的边（权值被调大了）都不会被割这样一个状态处取到。注意到因为原图的边权很小，所以我们加入图中的边权值只需要设成 $w$

即可。这样子我们只需要跑个 1024 次最大流就好了，但是还是不能过（hlpp，永远滴神！）。

最后一个优化，我们可以先把每条边都在图里删掉，然后跑一遍最大流，每次加边的时候就在残余网络里加边，由于我们加的边边权只有 $w$ ，所以额外增广次数就是 $nw$ 次，这样子跑的就快很多了。如果再狠一点的话，我们每次要求 $mask $ 的最小割时，我们可以在 $mask - lowbit(mask)$ 这张图的残余网络里加一条边再增广，这样又快很多了，但是不知道内存吃不吃得消。

至此，我们终于打过了 hlpp。