P3967 [TJOI2014] 匹配

二分图带权匹配必经边。为啥题解全是 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)$ 解决。