人类智慧

· · 个人记录

P3163

经典最大流建模，直接建模会有两个问题:

  1. 存在 a1->b2 和 b1->a2 。

  2. 一条双向边两边各走一次。

人类智慧地跑一遍 a1,b1->a2,b2 和一遍 a1,b2->a2,b1 的最大流，若其都满流，那么答案为Yes。

证明：

考虑第一遍有 a1->a2=an-x,b1->b2=bn-x,a1->b2=x,b1->a2=x ，又因为是双向边，所以第二遍依然能跑出 a1->a2=an-x,b2->b1=bn-x ， 也就有 a1->b1=x,b2->a2=x 。

此时观察上面得到的条件，会发现有 a1->b1=x，a1->b2=x ，根据双向边的性质，把 a1->b1 反过来，就有一条 b1->a1->b2=x 的路径，同时发现这不影响原来 a1->a2,b1->b2 的路径，所以 b1->b2=bn 满足了，a1->a2=an 也自然满足。

对于问题二，交换b1,b2前后，总有一次会限制边的流量，不用管。

三分网络

CF1558F

和 a_i 元素大小有关的题目，特别是这种神仙题，要果断猜结论：答案和大于 a_i 视为 1 ，小于 a_i 的视为 0 的序列有关。

然后接下来的问题虽然还是很复杂但是可做了许多。