建图的一些技巧

已经不止一次了解到建图的技巧了， 例如：

• 最大流建立超级源点，超级汇点
• 建反图，但已经忘了这个题是什么时候的题了
• 点权转成边权

2024/7/15 介绍点权转边权

如下所示，建立一个有 \(2N\) 个顶点和 \(N + M\) 条边（成本只分配给边）的有向图，答案就是从顶点 \(1_\text{in}\) 到顶点 \(i_\text{out}\) 的路径的最小成本。

• 对于原始图中的每个顶点 \(i\) ，创建两个顶点 \(i_\text{in}\) 和 \(i_\text{out}\) ，并添加一条代价为 \(A_i\) 的有向边 \(i_\text{in} \to i_\text{out}\) 。
• 为原始图中的每条边 \(u \leftrightarrow v\) 添加两条代价相同的有向边 \(u_\text{out} \to v_\text{in}\) 和 \(v_\text{out} \to u_\text{in}\) 。

使用 Dijkstra 算法可以在 \(O(M \log N)\) 时间内计算出最小成本。
这种方法也可用于其他目的。