如果他们俩中有一个人是快乐的,则另一个人也会变快乐.
求至少要多少天所有人都会变快乐,或者判断不可能所有人都变快乐.
那么根据裴蜀定理,有解的充要条件为每组内至少有一个人是快乐的.
首先有一个结论:如果 $n$ 个男生都快乐了,那么除非当前天数小于 $m$,否则所有女生一定也都是快乐的.这是因为往前的 $m$ 天里,由于所有男生都快乐了,因此要么是原本就都快乐,要么是快乐的影响另一个.
那么我们只需要求出最后一个变快乐的男生即可.为了方便,如果女生 $x$ 初始快乐,那么将男生 $x$ 也标记为初始快乐.
则最后所有点的最短路的最大值就是这一组的答案.
但是这样点数是 $10^9$ 级别的,无法承受.
如何进行连边呢?
我们要连三类边: