Contest5401 - 网络流-2
Published:
笔记
非常好文章：二分图与网络流 学习笔记
一些定义
- 匹配：没有公共点的边集
- 边覆盖：满足任意顶点都至少是一条边的端点的边集
- 点覆盖：满足任意边都至少有一个端点在集合内的点集
- 独立集：任意两点互不相连的点集
- 团：完全子图
图 $G = (V,E)$ 的补图：建出 $K_{ V }$ 后删掉所有 $E$ 中的边后的图
一些 NPC
- NPC 一般图最大独立集
- NPC 一般图最小点覆盖
- NPC 一般图最大团
- 一般图最大匹配 不是 NPC。
一些结论
- 最大团 = 补图最大独立集
- 最大流 = 最小割
- 平面图最大流 = 平面图最小割 = 对偶图最短路
- 最大独立集 + 最小点覆盖 = 总点数
- 二分图最小点覆盖 = 二分图最大匹配 = 总点数 - 二分图最大独立集
- 二分图最小带权点覆盖 + 二分图最大带权独立集 = 所有点权之和
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()$ 为最小割。
为什么是对的
- 割掉中转站的边，意味着使用这个中转站。
- 割掉用户的边，意味着舍弃这个用户。
- 未被舍弃的用户必须连着被割掉的中转站，从而导致图不连通。所以是求图的割。
- 所有用户的收益 - (被舍弃的用户 + 使用的中转站) = 利润。
- (被舍弃的用户 + 使用的中转站) 最小，利润最大。
E 卖猪
TODO:
F L型图形
TODO: