网络流一些基础建模

萌新入门网络流。

最小割模型很重要！

《切糕》

我们可以使用最小割表示选择。

此时考虑如果我们连一条 \(u\to v\) 权值为 \(\inf\) 的边表示什么？

那就代表了 \(s\leadsto u\) 与 \(v\leadsto t\) 不能同时成立。

这边给我们设置限制的方式！切糕就可以这么做了！

《开门大吉》

最开始以为是一样的，看了眼题解 wind_whisper大佬说这样就是对的。

但是很好奇呀，那个反向连无限权边！

这个可以结合起来看，现在实际上 \((u,v,\inf),(v,t,\inf)\) 这样限制的话会产生传递性 \((u,t,\inf)\) 如此的。

而对于一条链反连无限权边是出于限制“这条链每个边只能割一次”这样的。

---

对于两两产生贡献的题，我们构造这种形式的图：

\((s,a),(a,t),(s,b),(b,t),(a,b),(b,a)\)

这样割 \((s,a),(s,b)\) 表示都选第一种。

割 \((a,t),(b,t)\) 表示都选第二种。

割 \((s,a),(a,b),(b,t)\) 表示第一个选第一种，第二个选第二种的贡献。

然后可以解方程啦！

发现事实上这个只有不对称是产生贡献才会算出，所以一些问题我们可以把一些限制反向，变成对称产生贡献，。