NC24155. [USACO 2015 Dec B]Contaminated Milk

描述

输入描述

The first line of the input contains integers N, M,D, and S.

The next D lines (1≤D≤1000) each contain three integers p,m,tp,m,t, indicating that person p drank milk m at time t. The value of pp is in the range 1…N, m is in the range 1…M, and tt is in the range 1…100. A person may drink the same milk several times, and may also drink several types of milk at the same point in time.

The next S lines (1≤S≤N) each contain two integers p,tp,t, indicating that person p gets sick at time t. The value of pp is in the range 1…N, and tt is in the range 1…100. Each person gets sick at most once, and they only get sick because they drank the bad milk at some strictly earlier point in time.

输出描述

A single integer, specifying the minimum number of doses of medicine Farmer John needs to obtain so that he can guarantee that he will have sufficiently many doses to treat all the people who become sick, both during and after the party.

示例1

输入:

3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3
2 1 5
2 2 7
1 3
2 8

输出:

3

说明:

There are 3 people and 4 milk types. Person 1 gets sick at time 3 and person 2 gets sick at time 8. Person 3 does not get sick at the party, although we may still need to consider the possibility that he could become sick later, after the party ends. Let's consider the milk types one by one to see which ones could be contaminated; we know a milk type is potentially bad if everyone who became sick drank that milk type before becoming sick.

Milk 1: Both of the sick people (1 and 2) drank this milk before getting sick, so this could be the bad milk. If so, person 3 also drank it, so it would cause a total of 3 people to get sick (person 3 would become sick after the party).

Milk 2: Both of the sick people drank this milk before getting sick, so this could also be the bad milk. Nobody else drank this milk, so at worst 2 total people could be sick if this is the bad milk.

Milk 3: This cannot be the bad milk because person 1 did not drink it before getting sick -- person 1 drank it at time 4, and got sick at time 3. For milk 3 to be implicated in person 1 getting sick, person 1 would have needed to drink this milk by time 2 at the latest.

Milk 4: This cannot be the bad milk because person 2 did not drink it, and yet person 2 became sick.

The answer is therefore that Farmer John must obtain 3 doses of medicine, since if milk 1 is bad, then a total of 3 people will need to be cured.

原站题解

#include<bits/stdc++.h>
const int maxn=1e3+10;
using namespace std;
int n,m,k,t,d,s,he[maxn],he1[maxn],ma;
vector<pair<int,int> >person[maxn];
set<int>pk[maxn];
int main()
{
	int i,j;
	scanf("%d%d%d%d",&n,&m,&d,&s);
	while(d--)
	{
		int p,m,t;
		scanf("%d%d%d",&p,&m,&t);
		if(pk[p].find(m)==pk[p].end())
		pk[p].insert(m),he[m]++;
		person[p].push_back(make_pair(m,t)); 
	}
	for(i=1;i<=s;i++)
	{
		int p,m;
		set<int>ca;
		scanf("%d%d",&p,&m);
		for(auto q:person[p])
	    {
	    	if(q.second<m&&ca.find(q.first)==ca.end())
	    	he1[q.first]++,ca.insert(q.first);
		}
	}
	for(i=1;i<=m;i++)
	{
		if(he1[i]==s)
		ma=max(ma,he[i]);
	}
	printf("%d\n",ma);
	return 0;
}