Câmara de Compensação

Em uma cidade, muitas pessoas emprestam dinheiro para outras pessoas. A coisa chegou a um tal ponto que tem gente que é ao mesmo tempo devedor e credor. As pessoas resolveram então pagar suas dívidas e cada uma emitiu os cheques para pagar suas dívidas. Por exemplo, na figura, item (a), a pessoa C emitiu um cheque de 5 dinheiros para a pessoa A, e a pessoa D emitiu um cheque de 3 dinheiros para a pessoa C. Ou seja, a pessoa C recebeu da pessoa D e pagou a pessoa A. Pior ainda, existe um ciclo vicioso, em que a pessoa D emitiu um cheque de 3 dinheiros para a pessoa C, que por sua vez emitiu um cheque de 2 dinheiros para a pessoa B, que por sua vez emitiu um cheque de 1 dinheiro para a pessoa D. A situação mostrada no item (a) da Figura abaixo é descrita através de uma lista de cheques, com quatro triplas da forma (X, V, Y), para indicar que X emitiu um cheque de V dinheiros para Y . Na mesma Figura, no item (b), a situação é descrita com uma lista de apenas três cheques.

Entretanto, as duas listas são equivalentes: o saldo na conta bancária de uma pessoa é o mesmo em ambas as listas de cheques. Em ambos os casos, completada a compensação de todos os cheques, a pessoa A terminará com 5 dinheiros a mais na sua conta, a pessoa B terminará com 1 dinheiro a mais na sua conta, a pessoa C terminará com 4 dinheiros a menos na sua conta e a pessoa D terminará com 2 dinheiros a menos na sua conta.

Vamos então definir equivalência de listas de cheques emitidos: duas listas de cheques são equivalentes se, ao final do processo de compensação de todos os cheques, o seguinte vale para cada pessoa: seu saldo bancário ao final da compensação de uma lista é o mesmo que o saldo bancário da pessoa ao final da compensação da outra lista.

O total de valores compensados no item (a) da figura é igual a 11 dinheiros ao passo que no item (b) o total é de apenas 6 dinheiros! Este problema tem duas subtarefas:

• Subtarefa A: determinar, dada uma lista de cheques, se é possível ou não diminuir o total de valores compensados utilizando uma outra lista de cheques equivalente.

• Subtarefa B: determinar o total mínimo de valores compensados em uma lista de cheques equivalente. Você deve escrever um programa que resolva apenas a Subtarefa A ou que resolva as duas subtarefas.

Você deve escrever um programa que resolva apenas a Subtarefa A ou que resolva as duas subtarefas.