题解 P5029 【T'ill It's Over】
Wen_kr
·
·
题解
10 Pts
输出 0 或 n 都能得到十分。
0~20 Pts
rand()%2 == 1 output(1)
rand()%2 == 0 output(n)
20 Pts
#### 另外 10 Pts
使用网络流，暴力建图，$op = 1$，建立一条从 $a$ 到 $b$ 的边，跑 EK 即可。
#### 另外 20 Pts
考虑方案 2 和 3，建立两个虚拟节点，起点(可能有多个)向其中一个建立流量为无限大的边，另一个向终点(可能有多个)建立流量为无限大的边，然后从虚拟节点一个向另一个建立流量为这个方案使用次数限制的边。然后跑 EK 即可。
#### 70 Pts
使用 Dinic(或其他更加优秀的网络流算法)，其他如另外 20 Pts 的建图方式。
#### 100 Pts
考虑上一个连边方式的瓶颈，就是连接的节点数量为 $n$ 个，这不可以接受。
我们考虑使用线段树优化连边，这样连接的节点数量为 $log(n)$ 个，由于数据随机，Dinic(或其他更加优秀的网络流算法) 可以轻松跑过。