笔记
非常好文章：二分图与网络流 学习笔记
一些定义
- 匹配：没有公共点的边集
- 边覆盖：满足任意顶点都至少是一条边的端点的边集
- 点覆盖：满足任意边都至少有一个端点在集合内的点集
- 独立集：任意两点互不相连的点集
- 团：完全子图
- 图 \(G = (V,E)\) 的补图：建出 \(K_{|V|}\) 后删掉所有 \(E\) 中的边后的图
一些 NPC
- NPC 一般图最大独立集
- NPC 一般图最小点覆盖
- NPC 一般图最大团
- 一般图最大匹配 不是 NPC。
- NPC 三分图最大匹配（具体定义见 #6345. 特殊三分图匹配）
一些结论
- 最大团 = 补图最大独立集
- 最大流 = 最小割
- 平面图最大流 = 平面图最小割 = 对偶图最短路
- 最大独立集 + 最小点覆盖 = 总点数
- 二分图最小点覆盖 = 二分图最大匹配 = 总点数 - 二分图最大独立集
- 二分图最小带权点覆盖 + 二分图最大带权独立集 = 所有点权之和
A 吃饭
令食物点为 \(P\)，饮料点为 \(Q\)，牛点为 \(C\)。
- 把每个牛点 \(C_i\) 拆成两个点 \(C_{i,1}, C_{i,2}\)，连边 \(C_{i,1} \xrightarrow{1} C_{i,2}\)。
- 对每个食物点 \(P_i\) 连边 \(s \xrightarrow{1} P_i\) 和 \(P_i \xrightarrow{1} C_{j,1}\)。\(C_j\) 为喜欢 \(P_i\) 的点。
- 对每个饮料点 \(Q_i\) 连边 \(C_{j,2} \xrightarrow{1} Q_i\) 和 \(Q_i \xrightarrow{1} t\)。\(C_j\) 为喜欢 \(Q_i\) 的点。
跑最大流即可。
B 打扫卫生
建二分图，左部点是行，右部点是列。对于每个垃圾 \((x,y)\)，连 \(x \rightarrow y\)。
跑二分图最小点覆盖即可。
C 马
棋盘黑白染色，白格能攻击到的位置必然是黑格。
跑二分图最大独立集即可。
D 最大获利
一篇不错的题解：题解：P4174 [NOI2006] 最大获利
令中转站点为 \(P\)，用户点为 \(Q\)。
- 对每个 \(P_i\) 连边 \(s \xrightarrow{cost} P_i\)，其中 \(cost\) 为建这个中转站的代价。
- 对每个 \(Q_i\) 连边 \(A_i \xrightarrow{\infty} Q_i\)，\(B_i \xrightarrow{\infty} Q_i\)，\(Q_i \xrightarrow{income} t\)，其中 \(income\) 为收益。
跑最小割即可。
答案为 \((\sum income) - dinic()\)。其中 \(dinic()\) 为最小割。
为什么是对的
- 割掉中转站的边，意味着使用这个中转站。
- 割掉用户的边，意味着舍弃这个用户。
- 未被舍弃的用户必须连着被割掉的中转站，从而导致图不连通。所以是求图的割。
- 所有用户的收益 - (被舍弃的用户 + 使用的中转站) = 利润。
- (被舍弃的用户 + 使用的中转站) 最小，利润最大。