Cowntact Tracing

题目描述

在奶牛中爆发了高度传染性的牛病 COWVID-19 后，农夫约翰担心他的奶牛健康（照例编号为 $1 \ldots N$）。 最近，农夫约翰检测了所有奶牛，发现其中一些对疾病呈阳性。通过查看牛棚内的视频，他能够回顾奶牛之间近期的互动——结果发现奶牛互相打招呼时会进行“蹄握”（shake hooves），而这一动作不幸会使感染从一头奶牛传播到另一头。

农夫约翰整理出一份带时间戳的奶牛互动列表，每条记录形如 $(t, x, y)$，表示在时间 $t$，奶牛 $x$ 与奶牛 $y$ 进行了蹄握。

农夫约翰还知道以下事实： (i) 牧场上最初可能只有一头奶牛携带疾病（称这头奶牛为“零号病牛”，patient zero）。 (ii) 一旦一头奶牛被感染，她会在接下来的 $K$ 次蹄握中传播感染（这 $K$ 次蹄握中可能会多次与同一头奶牛接触）。在蹄握了 $K$ 次之后，她不再在后续蹄握中传播感染（因为此时她意识到自己在传播疾病，会认真清洗蹄子）。 (iii) 一旦一头奶牛被感染，她将一直保持感染状态。

不幸的是，农夫约翰既不知道 $N$ 头奶牛中哪一头是零号病牛，也不知道 $K$ 的取值！请根据他的数据帮助他缩小这些未知量的可能范围。保证至少存在一种可能是有效的。

输入格式

第一行包含 $N$ ($2 \leq N \leq 100$) 和 $T$ ($1 \leq T \leq 250$)。 下一行包含一个长度为 $N$ 的字符串，由 0 和 1 组成，描述农夫约翰的 $N$ 头奶牛当前的状态——0 表示健康奶牛，1 表示当前患病的奶牛。 接下来的 $T$ 行每行描述一条互动记录，包含三个整数 $t$, $x$, $y$：其中 $t$ 是互动发生的正整数时间（$t \leq 250$），$x$ 和 $y$ 是 $1 \ldots N$ 范围内的不同整数，表示在时间 $t$ 进行蹄握的两头奶牛。每个时间点最多发生一次互动。

输出格式

输出一行，包含三个整数 $x$, $y$, $z$：其中 $x$ 为可能成为零号病牛的奶牛数量，$y$ 为与数据一致的 $K$ 的最小可能值，$z$ 为与数据一致的 $K$ 的最大可能值（如果无法从数据中推导出 $K$ 的上界，则 $z$ 输出 "Infinity"）。注意 $K$ 可能等于 0。

4 3
1100
7 1 2
5 2 3
6 2 4

1 1 Infinity

提示

唯一可能的零号病牛是奶牛 1。对于所有 $K>0$，奶牛 1 会在时间 7 感染奶牛 2，而奶牛 3 和 4 保持未感染。

题目来源：Brian Dean

标签: USACO|2020|Bronze

来源

USACO|2020|Bronze