Programação Competitiva

(OBI2009, Fase 2, Nível 1)

Jimmy é um garoto muito esperto que adora música. No último mês ele ganhou um campeonato de um jogo cujo objetivo é tocar guitarra. Empolgado, Jimmy decidiu montar uma banda. Para Jimmy a banda perfeita tem quatro integrantes, ele e mais três: um baterista, um baixista e um cantor.

Agora Jimmy precisa encontrar os outros integrantes da banda. Para isto ele reuniu todos os álbuns que encontrou na internet e, após escutá-los diversas vezes, compilou o que ele chama de lista de entrosamento entre músicos. Nessa lista ele atribui, para cada par de músicos que já tocaram juntos, uma nota inteira de 1 a 100, que é uma medida de quão bem os músicos tocam juntos (o nível de entrosamento entre eles). Se dois músicos nunca tocaram juntos o nível de entrosamento é zero. Jimmy nunca tocou com nenhum músico da lista.

Jimmy pretende formar a sua banda a partir da lista de entrosamento entre músicos, da seguinte maneira: ele quer escolher os outros três músicos de tal forma que a soma dos níveis de entrosamento dos integrantes da banda seja a maior possível (ou seja, a soma dos níveis de entrosamento dos três pares possíveis de serem formados entre os três novos integrantes seja a maior possível).

Mas a lista de entrosamento entre músicos ficou muito grande e Jimmy não está conseguindo escolher os integrantes. Por isso, Jimmy está pedindo sua ajuda.

Tarefa

Você deve ajudar Jimmy a montar a melhor banda possível fazendo um programa que receba uma lista contendo o nível de entrosamento para cada par de músicos que já tocaram junto, e determine os músicos que formariam a melhor banda.

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 é formada por dois inteiros N e M , informando respectivamente o número de músicos (3 ≤ N ≤ 100) e o número de pares de músicos que já tocaram juntos (0 ≤ M ≤ 10⁴). Os músicos são identificados por números inteiros de 1 a N . Cada uma das M linhas seguintes contém três inteiros X, Y e Z, em que X e Y representa um par de músicos (1 ≤ X ≤ N , 1 ≤ Y ≤ N e X ≠ Y ) e Z representa o seu nível de entrosamento (1 ≤ Z ≤ 100). Cada par de músicos que já tocou junto aparece uma única vez na entrada.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo três números inteiros separados por espaço em branco, identificando os três outros músicos que devem compor a banda (em qualquer ordem). Se existir mais de uma melhor banda, Jimmy contenta-se com qualquer uma.

Exemplos

A questão pode ser acessada através do link: http://olimpiada.ic.unicamp.br/pratique/programacao/nivel1/2009f2p1_banda

Nesse link também existe a opção de testar o algoritmo desenvolvido e ver automaticamente se o algoritmo está correto (botão “Submete solução”). Entre as linguagens de programação disponível está Python, que é linguagem utilizada na codificação presente no vídeo.

Dica

“O número de vértices no grafo é pequeno (apenas 100). Logo, é possível verificar todas as combinações de 3 vértices. A solução é enumerar todas as combinações de 3 vértices, somar os pesos das arestas entre eles e escolher a combinação que maximize esta soma. A complexidade deste algoritmo é O(n3)O(n3). Note que, pelas restrições da entrada, sempre há uma resposta (o número de vértices é pelo menos 3)”.

Dica retirada de http://wiki.maratona.dcc.ufmg.br/index.php/BANDA09

Solução em C/C++

#include <stdio.h>

#define MAXN 101

int main() {
  int musicos[MAXN][MAXN], n, m, x, y, z;
  int aux = -1, sol[3];
  int i, j, k;
  
  scanf("%d %d", &n, &m);

  for (i = 0; i < m; i++) {
  	scanf("%d %d %d", &x, &y, &z); 
    x--; 
    y--;
    musicos[x][y] = z;
    musicos[y][x] = z;
  }

  for (i = 0; i < n; i++) {
    for (j = i+1; j < n; j++) {
      for (k = j+1; k < n; k++) {
		if (musicos[i][j] + musicos[i][k] + musicos[j][k] > aux) {
	  		aux = musicos[i][j] + musicos[i][k] + musicos[j][k];
	  		sol[0] = i; 
	  		sol[1] = j; 
	  		sol[2] = k;
		}
      }
    }
  }

  printf("%d %d %d\n", sol[0]+1, sol[1]+1, sol[2]+1);

  return 0;
}

Experimente esse código em: http://ideone.com/kkO3uj