Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2326
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2326
Sacoleiro
Por OBI - Olimpíada Brasileira de Informática 2007 
Brazil
Timelimit: 1
Seu amigo sacoleiro pediu sua ajuda num problema que ele está enfrentando. Ele tem um mapa de cidades que ele já conhece e que são interessantes para ele, além das rotas entre as mesmas. Ele pretende fazer uma viagem para comprar presentes para seu filho e para sua filha. O problema é que nem todos os presentes têm o mesmo preço, alguns são obviamente mais caros que os outros, e ele não quer ser injusto dando presentes mais caros para um ou para outro. O objetivo é fazer com que diferença entre a soma dos valores dos presentes seja a menor possível (de preferência que sejam iguais, naturalmente). Há, também, um limite de quanto ele pode gastar na viagem.
O sacoleiro tem um mapa com N cidades e as rotas que as ligam. Além disso, cada cidade pertence ao grupo A ou ao grupo B. No grupo A estão as cidades em que há presentes para o filho, enquanto que no grupo B estão as cidades com presentes para a filha. Sempre que ele para numa cidade ele pode comprar ou não o presente, mesmo que ele já tenha estado lá antes, inclusive pode comprar mais de uma unidade do mesmo presente (enquanto tiver dinheiro disponível, naturalmente). As cidades são numeradas de 0 a N - 1. O trajeto deve sempre começa na cidade 0. O tamanho do percurso não importa para o sacoleiro. O total disponível de dinheiro para os presentes é T. O sacoleiro não pode terminar a viagem sem ter comprado pelo menos um presente para algum dos filhos.
Escreva um programa que, dadas N cidades, as rotas entre elas e os valores de presentes de cada cidade, retorne qual a diferença mínima possível entre a soma dos presentes do grupo A e a soma dos presentes do grupo B.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N (2 ≤ N ≤ 30) que indica a quantidade de cidades. A segunda linha contém um inteiro T (10 ≤ T ≤ 100) que indica a quantidade de dinheiro que o sacoleiro tem para gastar. As N linhas seguintes contêm a descrição cada cidade. Cada uma dessas linhas tem o formato XPCKV0V1...VK-1, onde X é um inteiro que representa a cidade (numeradas de 0 a N - 1); P é um inteiro (1 ≤ P ≤ 10) que indica o valor do presente da cidade X; C é um caractere A ou B, indicando a que grupo a cidade X pertence; K é um inteiro (0 ≤ K < N ) que indica quantas rotas saem da cidade X; e cada Vi é um inteiro indicando um dos possíveis destinos a partir da cidade X. Note que as rotas não são bidirecionais. Uma cidade nunca terá rota para ela mesma e pode-se assumir que i ≠ j => Vi ≠ Vj.
Saída
Seu programa deve imprimir, na saída padrão, uma única linha com um inteiro representando a menor diferença possível de valores entre os presentes comprados para o grupo A e para o grupo B.
| Exemplo de Entrada | Exemplo de Saída |
|
4 |
1 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#define MAXN 31
#define MAXT 101
using namespace std;
vector<int> grafo[MAXN];
int processado[MAXN][MAXT][MAXT], n, t, resp, presente[MAXN], tipo[MAXN];
void dfs(int x, int a, int b) {
processado[x][a][b] = 1;
if (a || b) {
resp = min(resp, abs(a - b));
}
for (int i = 0; i < grafo[x].size(); i++) {
int v = grafo[x][i];
if (!processado[v][a][b]) dfs(v, a, b);
if (tipo[x] == 0) {
if (presente[x] + a + b < = t) {
if (!processado[v][a + presente[x]][b])
dfs(v, a + presente[x], b);
}
} else {
if (presente[x] + a + b <= t) {
if (!processado[v][a][presente[x] + b])
dfs(v, a, presente[x] + b);
}
}
}
}
int main() {
scanf("%d", &n);
scanf("%d", &t);
resp = MAXT;
for (int vez = 0; vez < n; vez++) {
int cidade, valor;
char letra;
int qtd;
scanf("%d %d %c %d", &cidade, &valor, &letra, &qtd);
presente[cidade] = valor;
tipo[cidade] = (letra == 'A');
while (qtd--) {
int vaipara;
scanf("%d", &vaipara);
grafo[cidade].push_back(vaipara);
}
grafo[cidade].push_back(cidade);
}
dfs(0, 0, 0);
printf("%d\n", resp);
return 0;
}
Input
20
0 9 A 2 1 2
1 8 B 1 2
2 7 A 1 3
3 6 B 1 1
Output