P3967 [TJOI2014] 匹配

_jimmywang_ · 2025-11-20 14:11:14 · 题解

二分图带权匹配必经边。为啥题解全是 4 次的。

这里用费用流比较好说明：先求出任意一种最大费用最大流，然后考虑一条匹配边 (u,v,w) 是否是必经边。如果不是，一定存在 v \to u 的一条增广路。注意此处和不带权的不一样的地方是，我们不仅要求增广路存在，而且这条增广路的费用必须是 -w。这样和 (u,v,w) 组成一个环后可以进行匹配状态翻转。

那么怎么求是否存在 v\to u，费用恰为 -w 的路径呢？考虑做完费用流以后，图中一定不存在正环，因为要是存在的话把这个环增广一下可以获得更大的总权值。因此如果存在 -w，一定是 v\to u 的最长路。因此我们把所有剩余容量为 1 的边的费用拉出来跑任意一个你喜欢的全源最长路算法即可。判定是否必经是简单的。

注意到后半的做法中剩余容量其实只和是否是匹配边有关，并不刚需残量网络。因此前一半找方案换成 KM 是可以的。因为 KM 是三次的，我们的最长路也给他配一个三次的 Floyd（而且非常好写），即可做到全局 O(n^3) 解决。