警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P3701」主席树 - 网络流

题意

传送门:洛谷 P3701 - 主席树

本题 AC 时间 190314,难度较低,见谅。

想起以前机惨、互膜都说别人 AC 了伪模板主席树,现在感觉好 naive 啧

解法

「伪模板」真是名不虚传……只不过是最大流的模板罢了……

显然,A 和 B 的 \(n\) 个人可以构成左部和右部,流量有无代表是否胜利。

然后你要求的是 A 最多胜利的场数,那么从 A 的每个人,向 B 中它可以打过的人,连一条流量为 \(1\) 的边。

然后从源点向每个 A 的人连一条流量为寿命的边,每个 B 的人向汇点连一条流量为寿命的边,跑一个最大流就好了。

还要记得给每个 J 加上同队 YYY 数量的寿命。

有两个坑:续命不会 -1s;答案对 \(m\) 取 min。

代码