Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2123
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2123
The Law Goes on Horseback!
By XI Maratona de Programação IME-USP, 2007 
Brazil
Timelimit: 1
The Royal Canadian Mounted Police is a very famous institution , whose origins date back to the nineteenth century. Your task is to bring the law to the farthest places in the continental country . Today the police have mounted a force of 25,000 men and about 5,000 horses .
Each seat of the RCMP has a horse farm where the animals are very well maintained and appointed the officers who have more affinity . This affinity is inferred in the observations of officers with several years of experience , watching the cops riding animals available . At the Fairmont Banff Springs Stables , where are the horses ridden by the police in the region of Banff Springs , it is necessary to solve the problem of deciding which soldiers will ride that horse . Note that a horse can be ridden by several policemen , but only a police officer riding a certain horse . Each horse has a limit of cops who can ride him. That means, in possession of affinity of several policemen who rode with the animals in recent times, we wish to find an assignment of the various police horses, so that the largest possible number of officers have a horse to ride.
Input
The entrance is composed of several instances. The first line of each instance consists of three integers n (1 ≤ n ≤ 100), m (1 ≤ m ≤ 100) and k (1 ≤ k ≤ 1000) indicating the number of horses, the number of soldiers and the number of affinities. The next line contains n integers c1, c2, .., cn indicating that the ith horse can ride ci (1 ≤ ci ≤ 100) soldiers. In the following k lines have two integers u (1 ≤ u ≤ n) and v (1 ≤ v ≤ m) indicating that there is affinity between u and v horse soldier.
The entry ends with end of file.
Output
For each instance, you must print an Instancia k identifier, where k is the number of the current instance. On the next line print the maximum number of officers who can take a horse to ride on an assignment.
After each instance print a blank line.
| Sample Input | Sample Output |
|
5 3 7 |
Instancia 1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <vector>
#define MAXN 101
using namespace std;
vector<int> grafo[MAXN], vis, capacidade;
vector < vector<int> > match;
int n, m, k, instancia;
int augmenting_path(int l) {
if (vis[l]) return 0;
vis[l] = 1;
for (int i = 0; i < grafo[l].size(); i++) {
int r = grafo[l][i];
if (match[r].size() < capacidade[r]) {
match[r].push_back(l);
return 1;
}
for (int j = 0; j < match[r].size(); j++) {
int p = match[r][j];
if (augmenting_path(p)) {
match[r][j] = l;
return 1;
}
}
}
return 0;
}
bool comp(int A, int B) { return capacidade[A] > capacidade[B]; }
int main() {
while (scanf("%d %d %d", &n, &m, &k) != EOF) {
printf("Instancia %d\n", ++instancia);
capacidade.assign(n + 1, 0);
for (int i = 1; i < = n; i++) {
scanf("%d", &capacidade[i]);
}
for (int i = 1; i < = m; i++) {
grafo[i].clear();
}
while (k--) {
int u, v;
scanf("%d %d", &u, &v);
grafo[v].push_back(u);
}
for (int i = 1; i < = m; i++) {
sort(grafo[i].begin(), grafo[i].end(), comp);
}
int resp = 0;
vector<int> vazio;
match.assign(n + 1, vazio);
for (int i = 1; i < = m; i++) {
vis.assign(m + 1, 0);
resp += augmenting_path(i);
}
printf("%d\n\n", resp);
}
return 0;
}
Input
1 1 1 1 1
1 1
1 2
2 1
2 2
2 3
4 3
5 3
Output
3