Contaminated Milk

题目描述

Farmer John 因其农场生产的牛奶质量而闻名，他正在为他的 $N$ 位最好的朋友举办一场品奶聚会（$1 \leq N \leq 50$）。\n不幸的是，聚会上提供的 $M$ 种牛奶中（$1 \leq M \leq 50$），恰好有一种变质了，但 Farmer John 不知道是哪一种！任何喝了变质牛奶的人之后都会生病，可能在聚会剩余时间内，也可能在聚会之后。\n给你一份聚会记录——谁在什么时候喝了哪种牛奶，以及谁在什么时候生病。基于这些信息，你可以推断哪些牛奶有可能是变质的。利用这一点，帮助 Farmer John 确定：为了保证能治好所有在聚会期间或之后生病的人，他至少需要准备多少剂药。

输入格式

输入格式（文件 badmilk.in）：\n第一行包含整数 $N$, $M$, $D$, 和 $S$。\n接下来 $D$ 行（$1 \leq D \leq 1000$），每行包含三个整数 $p, m, t$，表示编号为 $p$ 的人于时间 $t$ 喝了编号为 $m$ 的牛奶。$p$ 的取值范围是 $1 \ldots N$，$m$ 的取值范围是 $1 \ldots M$，$t$ 的取值范围是 $1 \ldots 100$。一个人可以多次喝同一种牛奶，也可以在同一时刻喝多种不同的牛奶。\n接下来 $S$ 行（$1 \leq S \leq N$），每行包含两个整数 $p, t$，表示编号为 $p$ 的人在时间 $t$ 生病。$p$ 的取值范围是 $1 \ldots N$，$t$ 的取值范围是 $1 \ldots 100$。每个人最多生病一次，并且他们生病的唯一原因是：在某个严格更早的时间点喝了变质的牛奶。

输出格式

输出格式（文件\nbadmilk.out）：\n输出一个整数，表示 Farmer John 至少需要准备多少剂药，才能保证无论哪些人在聚会期间或之后生病，他都有足够的药剂来治疗所有生病的人。

3 4 7 2\n1 1 1\n1 4 1\n1 3 4\n1 2 2\n3 1 3\n2 1 5\n2 2 7\n1 3\n2 8

3

提示

有 3 个人和 4 种牛奶。1 号在时间 3 生病，2 号在时间 8 生病。3 号在聚会期间没有生病，但我们仍需要考虑他在聚会结束后可能会生病的情况。我们逐一考虑每种牛奶，判断哪些可能被污染；若所有生病的人都在生病之前喝过该牛奶，则该牛奶就有可能是变质的。\n牛奶 1：两位生病的人（1 和 2）都在生病之前喝过这种牛奶，所以它可能是变质的。如果是这样，3 号也喝过它，因此总共会有 3 个人生病（3 号会在聚会结束后生病）。\n牛奶 2：两位生病的人都在生病之前喝过这种牛奶，所以它也可能是变质的。没有其他人喝过这种牛奶，因此若它变质，最坏情况下总共会有 2 个人生病。\n牛奶 3：它不可能是变质的，因为 1 号在生病之前并没有喝过它——1 号在时间 4 才喝，而在时间 3 就生病了。要让牛奶 3 导致 1 号生病，1 号最晚必须在时间 2 之前喝过它。\n牛奶 4：它不可能是变质的，因为 2 号没有喝过它，但 2 号却生病了。\n因此答案是 Farmer John 必须准备 3 剂药，因为如果牛奶 1 变质，那么总共会有 3 个人需要被治疗。\n题目来源：Austin Anderson 和 Brian Dean

标签: USACO|2015|Bronze

来源

USACO|2015|Bronze