一道一道记太浪费文章篇数了。

先记几种 dinic 的复杂度。

• 一般网络：\(O(n^2m)\)
• 各边容量为 \(1\) 的网络：\(O(m \min\{m^{\frac{1}{2}},n^{\frac{2}{3}}\})\)
• 二分图：\(O(m\sqrt n)\)

更详细的分析。

最大流

UVA10735 混合图的欧拉回路

存在欧拉回路的判断条件：每个点出度 = 入度。

定义一个点的权值为 \(a_u=in_{u}-out_{u}\)。

对于一条无向边 \((u,v)\)，先令其 \(u \rightarrow v\)。

考虑更改这条边的方向，会令 \(a_u+2,a_v-2\)。

若存在 \(a_u\) 为奇数，那么肯定不存在欧拉回路。

若 \(a_u<0\)，连边 \((u\rightarrow T,\frac{-a_u}{2})\)。

若 \(a_u>0\)，连边 \((S\rightarrow u,\frac{a_u}{2})\)。

对于一条无向边，连 \((u\rightarrow v,1)\)。

满流则有欧拉回路。

P5038 奇怪的游戏

假设最后所有数变为 \(x\)。

将棋盘黑白染色。

对于一个位置 \((i,j)\)，若 \(i+j\) 为奇数，则染黑色，否则染白色。

若黑白格子数目不同，那么 \(x\) 为黑白两颜色权值和之差。

否则二分这个 \(x\)。

对于黑点，连 \((u\rightarrow T,x-a_{u})\)。

对于白点，连 \((S\rightarrow u,x-a_{u})\)，设其周围的黑点为 \(v\)，连 \((u\rightarrow v,inf)\)。

满流即有解。

P3191 紧急疏散EVACUATE

由于有时间限制，将每个字符为 D 的点 \(v\) 拆为 \(v_i\)，表示 \(i\) 时刻的点 \(v\)。

对于一个字符为 . 的点 \(u\)，连边 \((S\rightarrow u,1)\)，表示这个位置有一个人。

bfs 求出到每个字符为 D 的点 \(v\) 的最短路 \(w\)，连边 \((u \rightarrow v_{w},1)\)，表示在 \(w\) 时刻，\(u\) 能到达门 \(v\)。

对于所有 \(v_i\)，连边 \((v_i \rightarrow T,1)\)，表示每个门每秒可以疏散一个人。

枚举当前时间为 \(t\)，对于所有 \(v\)，连边 \((v_{t-1}\rightarrow v_{t},inf)\)。

若满流，则可能撤离。

code jam world finals 2020 E Replace All(麻将机)

见11 月杂题题解。

最小割

P5934 最小生成树

以最小生成树为例。

考虑一个 kruskal 的过程，先按边权排序，对于当前边 \((u,v,L)\)，会用到这条边当且仅当 \(u,v\) 不在一个连通块。

那么加入所有 \(w<L\) 的边，以 \(u\) 为源点，\(v\) 为汇点，求最小割即可。

对于最大生成树同理。

两次求最小割加入的边集显然不重，把两次求的答案相加即可。

P4177 order

定义 \((u,v,w)\) 表示连有向边 \(u \rightarrow v\)，边权为 \(w\)。

对于每个工作 \(i\)，连边 \((S,i,x_i)\)，连边 \((i,a_{i,j},b_{i,j})\)。

对于每个机器 \(j\)，连边 \((j,T,y_i)\)。

如果割掉 \((S,i)\)，代表放弃这个工作。

如果割掉 \((j,T)\)，代表购买这个机器，否则不割，显然要割掉所有与 \(S\) 连通的 \((i,a_{i,j})\)。

可以发现是个二分图，复杂度 \(O(n^2\sqrt n)\)，随便跑。

CF311E Biologist

对于与 \(S\) 连同的点，为 0，与 \(T\) 连同的点，为 \(1\)。

那么对于一个点 \(u\)，若其为 0，连 \((S\rightarrow u,a_i)\)，如果割掉那么 \(u\) 就为 1，有转换代价 \(a_i\)。

对于一个全为 0 的要求 \(i\)，新建一个节点 \(p_i\)，连边 \((S\rightarrow p_i,W_i)\)，割掉则表示不满足这个要求。

然后对于要求的 \(k\) 个位置，连边 \((p_i\rightarrow k_j,inf)\)，这个依赖关系是不能割的。如果满足了这个条件，显然会割掉 \(k_j\rightarrow T\) 这些边。

对于一个全为 1 的要求，也类似，只不过要连向 \(T\)，\(k\) 个位置连 \((k_j\rightarrow p_i)\)。

对于赔钱，直接把割掉这条边的权值加 \(g\)。

费用流

P2469 星际竞速

关键词：每个点都要经过。

对于一个点，有两种到达方式，从边到和瞬移。

其实就是个最小路径覆盖，但是路径数 \(\leq n\)，求最小代价。

同最小路径覆盖的做法，每个点拆为 \(a_i,b_i\)。

对于一条有向边，连 \((a_u \rightarrow b_v,1,w)\)。

每个点连 \((S\rightarrow a_u,1,0),(b_u \rightarrow T,1,0)\)。

对于路径数 \(\leq n\) 的限制，新建一个超级源点 \(S'\)，连 \((S\rightarrow S',n,0)\)，对于每一个 \(u\)，连 \((S'\rightarrow b_u,1,A_u)\)。

此题可以直接 \((S\rightarrow b_u,1,A_u)\)。

P4542 营救皮卡丘

和上面一样的套路，最小路径覆盖，但是路径数 \(\leq k\)。

对于连边，floyd 求一下 \((u,v)\) 只经过 \(\leq v\) 的结点的最短路。