模拟赛被网络流打爆了。

题目来自于 。

二分图

LG1402 酒店之王

左边房子右边菜，搞出最大流就行了。

LGU64949 棋盘覆盖

棋盘黑白染色，可选的方块连边，搞出最大流就行了。

LGU64970 車的放置

行列为点，格子为边。

LG1129 矩阵游戏

如果有完美匹配，就可以。否则不行。

LG1963 变换序列

每个点最多对应两个 T，所以这是一个二分图最大匹配。字典序最小，只需要从后往前匈牙利就行了。

UVA1194 Machine Schedule

把图建出来，是二分图最小点覆盖。

二分图最小点覆盖 == 二分图最大匹配。

LG6062 Muddy Fields G

见过的套路题。先假设每个木板只能覆盖 1x1 的方块。可以节省的木板个数等于相通的边界数量。注意横竖边界不能同时消除。跑个最小割就行了。麻痹的看错题了操。

那就每个木板顶到头是最优的。把木板看成点，沼泽看成边，冲个最大流就行了。

LG3355 骑士共存问题

这题面都暗示了要黑白染色。

黑白染色，不能一起的点连边。冲一个最大独立集。

LG2423 朋友圈

原图的团，相当于在补图上找一个独立集。

观察题目连边的方式，A 国是个二分图，B 国是两个团，中间连了一些边。

对于 subtask1，直接在原图补图上找一个最大独立集即可。

对于 subtask2，发现 A 国最多选两个人。直接枚举，你惊奇地发现 B 的补图是个二分图。然后在 B 国解决类似问题即可。

UVA1327 King's Quest

本题可以看作最大匹配可行边的例题。

考虑在一个二分图中，\((u,v)\) 是最大匹配可行边需要满足以下条件之一：

• 1，\((u,v)\) 是匹配边。
• 2，设原图中 \(u\) 和 \(y\) 匹配，\(x\) 和 \(v\) 匹配。\((u,v)\) 不是匹配边，且删去 \((u,v)\) 之后，存在一条 \(x\rightarrow y\) 的增广路。

这种问题的解决办法是先求出一组完美匹配，然后匹配边反向，其余边正向。对于非匹配边，判断两端是否在一个连通块即可。因为 \(u\) 有且仅有一条来自 \(y\) 的入边，\(x\) 也有且仅有一条来自 \(v\) 的入边，所以存在 \(x \rightarrow y\) 的增广路等价于存在 \(v \rightarrow u\) 的路径。

本题中因为已经给出了一组完美匹配，直接 tarjan 就可以了。

LG2764 最小路径覆盖问题

拆点跑个最小割就行了。

LG2765 魔术球问题

首先考虑二分答案，计算当前球数量最少需要多少个柱子。

比较容易想到拆点二分图，符合条件的两个球之间连一条边，冲个最小割就行了。

最大流

LG2472 蜥蜴

把柱子拆成入点出点，中间连权值的边。直接冲个最大流就行了。

套路：点有权值的时候拆点，转化为边的权值。

LG2766 最长不下降子序列问题

第一问

乱搞。随便 dp。

第二问

把真正的贡献图搞出来，拆点。

有贡献边的连上，直接冲最大流。

第三问

把和 1，\(n\) 相邻的边的流量搞成 INF，然后再冲个最大流。

LG2754 家园 / 星际转移问题

二分答案。（当然由于 dinic 的神秘性质，从小到大枚举时间然后在残量网络上跑更优）。

记 \((x,t)\) 表示 \(t\) 时刻的 \(x\) 点。飞船可以看作先让所有人下车，然后再看是否让所有人上车。

对于飞船某天的起点 \(x\)，终点 \(y\)，连 \((x,t) \rightarrow (y,t+1)\)，容量是飞船大小。

连 \((x,t) \rightarrow (x,t+1)\)，容量 INF，表示呆在星球上不动。

UVA1660 Cable TV Network

枚举两个可能不相邻的点对，计算它们不相邻的最小贡献。

注意到只能割点，相当于点的权值为 1，把点拆成入点和出点，建出原图。跑 \(x \rightarrow y\) 的最大流就是这个点对的答案。

LG2774 方格取数问题

黑白染色，发现只有不同颜色的点会影响。

在原图上连边 INF，连边 \((S,black,w_{black}),(white,T,w_{white})\) 。

冲个最小割就行了。

LG2057 善意的投票

源点连想睡觉的人，不想睡觉的人连汇点。朋友之间连双向边。

图的意义：跑完最小割之后，图分成了两个集合。割开的边代表冲突。

LG2598 狼和羊的故事

源点连羊，狼连汇点。相邻两个方块之间连边。

还是考虑图的意义：狼在一个集合，羊在一个集合，割掉的边表示矛盾。

LG4126 最小割

先求出一个最大流。可行边一定满流，否则在某条增广路上有一个更优的割边。

可行边：残量网络中不存在 \(x \rightarrow y\) 的路径 (tarjan)。

必须边：残量网络中存在 \(S \rightarrow x,y \rightarrow T\) 的路径。

LG2046 海拔

对偶图

当一个图 \(G = \{V,E\}\) 可以在平面上画出，并且边的交点仅有端点时，称为平面图。

平面图所在的平面会被边分割成若干个面。

对偶图 \(G = \{V,E\}\) 的点集是平面图的面。在相邻两个面之间有边，权值是这两个面间的边的权值。

对偶图在网络流中的应用

如果网络流图是一个平面图，那么在 \(S\) 和 \(T\) 之间连一条虚拟边。然后在这个虚拟图上建立对偶图。那么从 \(S'\) 到 \(T'\) 的最短路就是原网络流图的最小割。

本题

直接手建对偶图即可。

LG3749 寿司餐厅

感觉 \(m=0\) 的时候显然可以冲个 dp，但是很奇怪题解都没提到这个。

把区间向子区间连边，然后每个食物向种类连边。冲一个最大权闭合子图就行了。

费用流

LG2045 方格取数加强版

把点拆成入点，出点。中间连 \((1,w),(INF,0)\) 的边，分别表示第一次走和随便乱走。相邻两个点之间连 \((INF,0)\) 表示可以到达。冲个 MCMF 就行了。

LG2053 修车

倒数第 \(i\) 个修会搞出 \(t_i \times i\) 的贡献。

知道自己倒数第几个被修就好做了。把工人 \(i\) 拆成 \((i,j)\)，表示倒数第 \(j\) 个被修，然后随便连一连、匹配一下，就做完了。

LG2050 美食节

上面这玩意的数据加强版。

注意到每个师傅一定会用一个连续的区间，所以一边增广一边动态开点就行了。

LG2604 网络扩容

第一问直接最大流。

第二问在残量网络上瞎搞搞，原来有的边的费用为 0，再加一条 \((INF,w)\) 的边。

LG2153 晨跑

拆点直接冲 MCMF。

咕