Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2008
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2008
Exposing Corruption
By Walter Erquínigo Pezo 
Peru
Timelimit: 1
The Central Committee in Nlogonia is formed by many congress members. As the political system is dichotomic, each congress member belongs to one of two parties: the Deadly Serious Party and the Party! Party! Party. Historical tradition calls them DSP and PPP, respectively.
Edward is an investigative journalist. He discovered that congress members are corrupt and will switch parties if offered a given amount of Nlogmoney to do so. Each congress member has his or her own specific price, but they all have a price. As usual in politics, there exist rivalries between some pairs of congress members. Rivals would never accept to be in the same party.
Edward has a budget and wants to use it to make some congress members switch parties, thus gathering indisputable evidence for his investigation. In doing so, he has to respect rivalries: after everyone who was offered money switches, rivals must be left belonging to different parties.
Edward wants to cause maximum impact. Can you help him find out the maximum number of congress members that can belong to DSP if he uses at most all of his budget towards that goal? Similarly, what is the maximum number of congress members that can belong to PPP under the same constraints?
Input
The input contains several test cases; each test case is formatted as follows.
The first line contains four integers D, P, R and B, representing respectively the number of congress members that initially belong to DSP (1 ≤ D ≤ 100), the number of congress members that initially belong to PPP (1 ≤ P ≤ 100), the number of rivalries among congress members (1 ≤ R ≤ 2000), and the budget of the journalist expressed in Nlogmoney (1 ≤ B ≤ 104 ). Members of DSP are identified with distinct integers from 1 to D, while members of PPP are identified with distinct integers from 1 to P. The second line contains D integers S1, S2, . . . , SD, indicating that member i of DSP will switch parties if offered Si Nlogmoney (1 ≤ Si ≤ 100 for i = 1, 2, . . . , D). The third line contains P integers T1, T2, . . . , TP , indicating that member j of PPP will switch parties if offered Tj Nlogmoney (1 ≤ Tj ≤ 100 for j = 1, 2, . . . , P). Each of the next R lines describes a rivalry with two integers X and Y , representing that member X of DSP and member Y of PPP are rivals (1 ≤ X ≤ D and 1 ≤ Y ≤ P).
Output
For each test case in the input, output a line with two integers representing the maximum number of congress members that can belong to DSP using the given budget and, similarly, the maximum number of congress members that can belong to PPP using the given budget.
| Input Samples | Output Samples |
|
2 3 2 55 |
3 4 |
|
3 2 6 30 |
3 3 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 2 * (1e3 + 1);
const int MAXB = 1e4 + 1e3;
int pai[MAXN], custo[MAXN], membros_dsp[MAXN], membros_ppp[MAXN], tam[2];
vector<int> valor[2], despesa[2];
int dp[MAXN][MAXB][2];
int D, P, R, B, N;
int find(int x) {
// printf("Trying to find parent %d\n",x);
if (x == pai[x]) {
// printf("Found\n");
return x;
}
// printf("Recursion\n");
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
// printf("Trying to join %d %d\n",x,y);
if (x == y) return;
if (custo[x] > custo[y]) {
custo[x] += custo[y];
membros_dsp[x] += membros_dsp[y];
membros_ppp[x] += membros_ppp[y];
pai[y] = x;
} else {
custo[y] += custo[x];
membros_dsp[y] += membros_dsp[x];
membros_ppp[y] += membros_ppp[x];
pai[x] = y;
}
// printf("Joined\n");
}
int solve(int obj, int aguenta, int tipo) {
// printf("Obj %d Aguenta %d Tipo %d\n",obj,aguenta,tipo);
if (obj >= tam[tipo]) return 0;
// printf("Padrao passou\n");
if (dp[obj][aguenta][tipo] != -1) return dp[obj][aguenta][tipo];
// printf("Temos que calcular\n");
int nao_coloca = solve(obj + 1, aguenta, tipo);
if (despesa[tipo][obj] < = aguenta) {
int coloca = valor[tipo][obj] +
solve(obj + 1, aguenta - despesa[tipo][obj], tipo);
// printf("DP[%d][%d][%d] =
// %d\n",obj,aguenta,tipo,max(nao_coloca,coloca));
return dp[obj][aguenta][tipo] = max(coloca, nao_coloca);
}
// printf("DP[%d][%d][%d] = %d\n",obj,aguenta,tipo,nao_coloca);
return dp[obj][aguenta][tipo] = nao_coloca;
}
int main() {
scanf("%d %d %d %d", &D, &P, &R, &B);
N = D + P;
for (int i = 1; i < = D; i++) {
scanf("%d", &custo[i]);
pai[i] = i;
membros_dsp[i] = 1;
}
for (int i = D + 1; i < = N; i++) {
scanf("%d", &custo[i]);
pai[i] = i;
membros_ppp[i] = 1;
}
while (R--) {
int u, v;
scanf("%d %d", &u, &v);
join(u, D + v);
}
for (int i = 1; i < = N; i++) {
if (find(i) == i) {
if (membros_dsp[i] < membros_ppp[i]) {
valor[0].push_back(membros_ppp[i] - membros_dsp[i]);
despesa[0].push_back(custo[i]);
} else if (membros_dsp[i] > membros_ppp[i]) {
valor[1].push_back(membros_dsp[i] - membros_ppp[i]);
despesa[1].push_back(custo[i]);
}
}
}
tam[0] = valor[0].size();
tam[1] = valor[1].size();
// printf("%d %d\n",tam[0],tam[1]);
memset(dp, -1, sizeof(dp));
printf("%d %d\n", D + solve(0, B, 0), P + solve(0, B, 1));
return 0;
}
Input
20 30
40 30 1
2 3
1 3
Output