#P18932. [2026多校联测]传输
[2026多校联测]传输
传输
题目描述
某数据中心有 台服务器,编号从 到 。服务器之间由 条单向数据传输线路连接。 号服务器是源服务器,从它出发可以沿一条或多条线路到达其他所有服务器。
一名黑客准备在某个服务器上投放一种会自我复制的恶意程序。程序会从该服务器出发,沿着单向数据传输线路不断感染其它服务器。被程序感染的服务器数量称为感染规模。
管理员提前得知了黑客的计划,他可以在 台服务器上部署防火墙。部署防火墙的服务器不会被感染,也不会继续传播恶意程序。
管理员会先选择至多 台服务器部署防火墙,以尽可能降低最坏情况下的感染规模。之后,黑客会选择一台服务器投放程序,并使感染规模尽可能大。你的任务是计算最终的感染规模,即最终会被恶意程序感染的服务器数量。
输入格式
输入的第一行包含两个正整数 和 ,表示服务器数量和管理员可以部署的防火墙数量。
接下来有一行包含 个整数 ,其中 表示存在一条单向数据传输线路从 号服务器通往 号服务器。
输出格式
输出一行一个整数表示答案。
样例 1 输入
5 2
1 2 1 1
样例 1 输出
1
样例 2 输入
7 1
1 1 2 2 3 3
样例 2 输出
3
样例 3 输入
7 2
1 2 2 4 1 6
样例 3 输出
2
样例 4
见选手目录下的 transmit4.in 与 transmit4.ans。
样例 5
见选手目录下的 transmit5.in 与 transmit5.ans。
样例 6
见选手目录下的 transmit6.in 与 transmit6.ans。
样例 7
见选手目录下的 transmit7.in 与 transmit7.ans。
数据范围
对于所有测试数据,保证:。
| 测试点编号 | 特殊性质 | |
|---|---|---|
| 无 | ||
| A | ||
| ^ | B | |
| 无 |
- 特殊性质 A:对于所有 ,有 。
- 特殊性质 B:。