Дан неориентированный связный граф состоящих из n вершин и m ребер.
Рассматривается все пути начинающейся из вершине номер 1 и заканчивающейся на n.
Как найти все такие вершины который встречается неизбежно на пути от 1 до n?
1<=n<=20000, 1<=m<=200000.
1 2013-10-15 12:49:20
Тема: Помогите с задачей (0 ответов, оставленных в Problems)
3 2013-06-18 20:25:26
Тема: Problem (3 ответов, оставленных в Problems)
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.