最小割建模

\(\bullet\) \(\texttt{[国家集训队]圈地计划}\)

\(\bullet\) \(\texttt{[SCOI2012]奇怪的游戏}\)

闭合子图建模

\(\bullet\) \(\\texttt{[ARC085C] MUL}\)

板子题，每个编号的宝石向它的倍数编号连边，边数 \(O(n \ln n)\)，然后就变成了求最大权闭合子图。

具体做法是源点向正权点连流量为点权的边，原图的边流量设为 inf，负权点向汇点连容量为 |点权| 的边，答案即为正权点点权和减去最小 \(S-T\) 割。

\(\bullet\) \(\texttt{[NOI2006] 最大获利}\)

板子题，同上。

匹配问题

\(\bullet\) \(\texttt{CF628F Bear and Fair Set}\)