图论建模做题笔记

MaxFwl · 2025-02-09 11:26:35 · 个人记录

二元关系最小割模型，即每个元素有两种取值，对于若干组 x = a, y = b，获得 c 收益，最大化总收益。

考虑将每个点向源点与汇点连边，表示两种不同的取值，若有 x 与 y 之间的限制，就在 x 至 y 间连边，边权可以解方程求出。

容易想到建立分层图，为表示删除一个点，可以把一个点拆成出点和入点，然后直接跑最小割即可算出第一问答案。

一条边 (u, v) 最小割的可行边，等价于跑完最大流之后没有 u 到 v 的增广路。

求最小字典序最小割，考虑直接贪心，若碰到可行边，直接将它加入割边集，然后删掉它重新做一遍最小割即可。

最大密度子图问题。

考虑到答案的形式，容易想到 01-分数规划，于是问题转化为选择一条边获得 1 的收益，选择一个点付出 mid 的代价，是否能使总收益非负。

我们发现选择一条边必须选择它的两个端点，于是就可以转化为最大权闭合子图问题，使用最小割解决。

若攻击路线可以相交，那么直接攻击能攻击到的收益最大的位置即可，但是攻击路线不能相交，这种冲突关系提示了可以使用最小割刻画反悔的过程。

于是我们对每个普通点拆点，一个表示被横向攻击，一个表示被纵向攻击，两点之间连一条不可割的边，同时对于每个横向攻击的炮塔向 S 连边，反之向 T 连边。

我们考虑如何刻画反悔的过程，容易想到若要在点 (x, y) 停止，下一个被攻击到的点为 (nx, ny)，那么就等价于割掉这两个点之间的边，边权则应该为可以获得的最大收益 z 减去 a_{x, y}，于是就做完了。

平面图最小割等于对偶图最短路，建对偶图跑 dijkstra 即可。

容易想到使用最小费用最大流解决该题。

考虑如何建图使得每天需要 r_i 条餐巾的限制转化为流最大的限制，我们将每一天拆成两个点，一个点表示一天开始，另一个表示一天结束，然后将表示开始的点连向汇点，建容量为 r_i，再从源点连一条同样的边到表示结束的点。

考虑这样为什么是对的。我们发现一定可以使得所有连向汇点的边满流，并且源点连出的边可以将这部分失去的流量补回。

容易发现，在这样的图中，一天开始的点对应的是干净毛巾，而一天结束的点对应的是脏毛巾，于是余下的限制是容易刻画的。

上下界网络流模板题，但是我们考虑用费用流做。

考虑模仿 P1251，本题的限制是每条边至少被经过 1 次，于是可以对每条边拆点。

余下的限制都已经是图的形式，不需要进行转化，可以直接模拟，记得将源点向初始点连边补足流量即可。

不等式差分模型。

笔者目前还没学懂，先咕了。

如果考虑它的逆置换 Q，容易发现性质：

Q 中的 (u, v) 若满足 |u - v| < k，则它们的相对位置永远不变。

所以，对于点对 (u, v) 满足 |u - v| < k，p_u 与 p_v 的相对大小关系不变。

根据相对大小，可以建边，转化为求字典序最小拓扑序，但是建图肯定不行，可以考虑线段树维护当前是否有入边即可。