自动搬运

查看原文

来自洛谷，原作者为

	Wen_kr 谢谢你。

搬运于2025-08-24 22:06:22，当前版本为作者最后更新于2018-11-14 07:54:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

10 Pts

输出 0 或 n 都能得到十分。

0~20 Pts

rand()%2 == 1 output(1)
rand()%2 == 0 output(n)

20 Pts

$n = 1$，考虑建出一张图，判断从 1 号点能否到 k 号点即可。

另外 10 Pts

使用网络流，暴力建图，$op = 1$，建立一条从 $a$ 到 $b$ 的边，跑 EK 即可。

另外 20 Pts

考虑方案 2 和 3，建立两个虚拟节点，起点(可能有多个)向其中一个建立流量为无限大的边，另一个向终点(可能有多个)建立流量为无限大的边，然后从虚拟节点一个向另一个建立流量为这个方案使用次数限制的边。然后跑 EK 即可。

70 Pts

使用 Dinic(或其他更加优秀的网络流算法)，其他如另外 20 Pts 的建图方式。

100 Pts

考虑上一个连边方式的瓶颈，就是连接的节点数量为 $n$ 个，这不可以接受。

我们考虑使用线段树优化连边，这样连接的节点数量为 $log(n)$ 个，由于数据随机，Dinic(或其他更加优秀的网络流算法) 可以轻松跑过。