网络流

经典模型

二分图最大匹配/最大权匹配

最大权匹配等价于拆点后的最大匹配， $S\xrightarrow{a_x} x\xrightarrow{\infty} y\xrightarrow{a_y} T$ 。

二分图的一些东西，最大匹配 $=$ 最小点覆盖 $=n\ -$ 最大独立集 $=$ $n\ -$ 最小边覆盖。

最小链覆盖/最小路径覆盖

拆成入点出点，每条边都是出点向入点连边，然后变成最大匹配，答案是 $n\ -$ 最大匹配。

理解起来就是初始每个点自己是一条路径，每个匹配相当于接起来两条路径。

若路径之间可以重复点，那相当于不能重复点但是能往前跳任意步，传递闭包之后再做就可以了。

也可以不传递闭包，只需要每个点入点向自己的出点连 $\infty$ 的边，表示可以跨过这个点。

最长反链：偏序集（传递闭包图）上两两不可达的最大集合，它等于最小链覆盖。

偏序集最大独立集

等于最长反链。

偏序集最大权独立集：[ABC354G] Select Strings，等价于拆点后的最大独立集，然后一路转成 $\sum a_i\ -$ 最大权匹配。

最小割

文理分科/带权2-sat

每个点要么文要么理，同桌之间若干组合会产生价值，可以用 $S\xrightarrow\inf x\xrightarrow\inf T$ 的模型， $\rm inf$ 是数量级介于 $\infty$ 和 $c$ 之间的数，使用它是为了防止为了逃避贡献同时割掉两边，两个点之间的贡献是好处理的。

等价于每个逻辑命题要么成立要么不成立，若有两个逻辑命题满足某种关系就产生某种价值。

p.s. 有一种简单的情况有更简单的图，即所有限制形如（ $a,b$ 不能分家， $a$ 必须选文， $a$ 必须选理）中的一个，此时直接把必须选文的连 $S$ ，必须选理的连 $T$ ，不能分家的连双向边，不过这种情况似乎可以线性处理。

把价值改为 $\infty$ 就是正常的逻辑 2-sat。

2-sat 指的是 $(x_1\vee x_2)\wedge (x_3\vee,x_4)\wedge\cdots$ ，用 $\vee$ 连接的逻辑命题至多两个，但是 $\wedge$ 可以任意连接。

但有时候不仅仅 2-sat 才能用该模型，很多时候我们可以把好几种选择给拆成几个二元逻辑命题，然后证明不存在非法情况/非法情况必定不优来达成我们的目的。

例：CF1666K Kingdom Partition

给定一个无向图，你要把点分成三部分，对于一条边权为 $l$ 的边，设 $a_i$ 是点 $i$ 在的集合：

若 $a_u,a_v=1\vee a_u,a_v=2$ ，则贡献为 $2l$ 。

若 $a_u=3\wedge (a_v=1\text{ or }2)$ ，则贡献为 $l$ 。

同时强定 $a_x=1,a_y=2$ ，求最小总贡献并构造方案。

$n\le 1000,m\le 2000$ 。

三个集合，一看傻眼了。

不要急，先硬拆。

设 $x_i=[a_i=1],y_i=[a_i=2]$ ，那非法情况是 $x_i=y_i=1$ 的情况。

根据最小割的定义，我们要最小化这个式子：

$\sum_{(u,v,w)}w\cdot x_u\cdot(1-x_v)$

$x$ 都是布尔变量，且 $x_S=1,x_T=0$ 。

也就是说代价关于 $x$ 其实是一个线性的关系，根据我们的定义不难得到 $[a_i=3]=1-x_i-y_i$ ，那我们可以推算出 $x=y=1$ 的点连了一次 $A$ ，连了一次 $B$ ，连了 $-1$ 次 $C$ 。

称其为 $D$ 类点，那么其连边贡献为：

$D\leftrightarrow A:2l+0-l=l\\D\leftrightarrow B:0+2l-l=l\\D\leftrightarrow C:l+l-0=2l\\D\leftrightarrow D:l+l-2l=0$

你发现贡献跟 $C$ 一模一样，所以我们可以容忍 $D$ 的存在，最后把 $D$ 全换成 $C$ 就是答案。

但我们连边还要把形式变成每个布尔变量是否成立的形式，把贡献列出来：

$2lx_ux_v+2ly_uy_v+l(1-x_u-y_u)(x_v+y_v)+l(1-x_v-y_v)(x_u+y_u)$

暴力展开化简（手推柿子别写 $l$ ，会和括号混在一起的）得到 $wx_u+wx_v+wy_u+wy_v-2wx_uy_v-2wx_vy_u$ 。

合并可以得到 $wx_u(1-y_v)+wx_v(1-y_u)+wy_u(1-x_v)+wy_v(1-x_u)$ ，当然你也可以硬使用上面的式子，先把答案减掉 $4w$ ，然后只要没选 $x_uy_v$ 就获得 $2w$ ，另一边同理。

观察到限制全部形如不能分家，此时可以使用上面说的简单模型。

切糕模型

类似修车，我们将每个点的每个值拆点，用一条链串起来，割哪条就表示选了哪个值，然后对于若 $x\ge a$ ，则 $y\ge b$ 这样的限制就可以使用 $(x,a)\to(y,b)$ 。

例：[ARC107F] Sum of Abs

$N$ 个点 $M$ 条边的无向图，每个点有两个权值 $A_i$ 和 $B_i$ 。可以用 $A_i$ 的代价删除第 $i$ 个节点。并删除与这个点相连的边。一个极大连通块的权值定义为 $B_i$ 的权值和的绝对值。

删除一些节点后，收益定义为所有极大连通块权值之和减去代价和。求最大的可能收益。

$n,m\le 300$ 。

每个点最终的贡献有三种：

被删了： $-a_i$ 。
正贡献： $b_i$ 。
负贡献： $-b_i$ 。

我们发现绝对值并不重要，只需要同一个连通块里的点（有边相连的点）的正负性一样即可。

所以我们使用切糕模型，用正——删——负串起三个点，只需限制一个人是负时另一个人不能是正。

负贡献问题并不大，可以整体偏移。

最小费用流

CF1288F Red-Blue Graph

有一张二分图，左边有 $n_1$ 个点，右边有 $n_2$ 个点， $m$ 条边。每个点可能有一种颜色 R 或者 B，也可能没有，也就是 U。现在要给一些边染色，把边染成 R 要花费 $r$ 的代价，把边染成 B 要花费 $b$ 的代价，要求对于每个颜色为 R 的点，与之相邻的边中 R 的边严格多于 B 的边；对于每个颜色为 B 的点，与之相邻的边中 B 的边严格多于 R 的边。求花费最小的方案，输出任意一种，无解输出 $-1$ 。其中 $1 \le n_1, n_2, m, r, b \le 200$ 。

注意边可以不染，此时不消耗任何代价。

若我们用流量来表示红蓝边的数量，则本题显然不是最大流，也不是最小费用最大流，所以我们要按照最小费用流去想。

这种严格多于很好搞，点是红的就 $S\to x$ 流 $\ge 1$ 的流量，点是蓝的就 $x\to T$ 流 $\ge 1$ 的流量，红红/红灰/蓝蓝/蓝灰相当于用价钱“购买”流量，红蓝边相当于流量的转移。

跑有源汇上下界最小费用流即可。