1

Тема: Problem

Any idea please:

There are N providers and M internet users in your town. Every user needs internet, but does not need more than one provider. Every user knows, what providers are available to him. Every provider can accept connections from not more than Ki users. You must find the maximal quantity of users, that can be connected to internet at the same time.

Input
The first line contains two integers N (1 ≤ N ≤ 50) and M (1 ≤ M ≤ 500). The second line contains N numbers Ki (1 ≤ Ki ≤ 50). Each line of next M lines contains a lists of providers, available for corresponding user - a set of nonrepeating numbers from 1 to N, separated by single spaces. List of providers is terminated by zero.

Output
Output one number - maximal quantity of users online.

2

Re: Problem

Find maximum flow in this graph, where additionally N vertices are connected with the source vertex with edges with capacity=1, and M vertices are connected with the sink vertex with edges with capacity=Ki.

3

Re: Problem

Thank you

4

Re: Problem

Hello everyone. I have just encountered with this problem and I have solved it with Edmonds- Karp's maximal flow algorithm.
But got TLE(Time Limit Exceeded) verdict. What algorithm must I use to avoid TLE? Please give me an idea. Thank you in advance.