Caminho Aumentante em Grafo Ponderado com BFS

Faça um programa que leia um grafo ponderado e dois vértices s e t Calcule o primeiro caminho aumentante de um vértice s até um vértice t usando uma busca em largura BFS Calcule o resultado do primeiro aumento de fluxo usando o caminho aumentante encontrado Considere o fluxo inicial zero Entrada Recebe n m s e t n é o total de vértices m o total de arcos s é a fonte e t é o sumidouro A seguir m linhas cada linha com um trio de inteiros correspondentes ao início e fim do arco seguido do peso do arco Os vértices são identificados de 0 até n1 Saída Linha 1 imprime o caminho aumentante O formato do caminho é i j peso Linha 2 imprime a capacidade deste caminho Imprima também o resultado de aumentar o fluxo com este caminho aumentante Linha 3 imprime a matriz de fluxo Linha 4 imprime a matriz de adjacência da rede residual resultante após o aumento do fluxo Exemplo Entrada 6 9 9 5 0 1 16 0 2 3 1 3 12 2 1 4 2 4 14 3 2 9 3 5 20 4 3 7 4 5 4 Saída 0 1 16 1 3 12 3 5 20 12 0 12 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 4 0 0 0 14 0 12 9 0 0 8 0 0 7 0 4 0 0 0 12 0