Eu estou tentando resolver um exercício que está nesse link aqui: https://br.spoj.com/problems/REDOTICA/
Eu fiz um algoritmo para isso, porém não está retornando o que deveria.
O teste que eu fiz que retornou os valores errados, foi com os seguintes valores:
n2=3
m3=3
vet[0][0]=1 ; vet[0][1]=2 ; vet[0][2]=10
vet[1][0]=1 ; vet[1][1]=2 ; vet[1][2]=10
vet[2][0]=1 ; vet[2][1]=2 ; vet[2][2]=10
Era para retornar no final:
Teste 1 Menor!!!: 20
2 3
3 1
Porém, por alguma razão está retornando:
Teste 1 Menor!!!: 20
1 2
2 3
3 1
Eu tentei resolver o problema da questão da seguinte maneira:
criei a função caminho() para fazer todas as combinações possíveis de conjunto de caminhos diretos entre duas vilas. Depois criei a função verificar() para verificar se esses caminhos são válidos. Na função caminho(), a cada combinação achada, ela vai chamar a função verificar() para saber se essa combinação é válida, ou seja, se essa combinação consegue conectar todas as vilas entre si.
Coloquei vários System.out.println() para facilitar na identificação do erro e percebi que o vetmenor[] (vetor que guarda combinação de caminhos válida que causa menos danos ao meio ambiente) em um certo momento do código, acha a combinação certa que é:
vetmenor[]=[ 0, 1 ,1 ]
Mas logo depois ele muda o vetmenor[] para vetmenor[]=[ 1, 1, 1]. Sendo que eu marquei com System.out.println todos as linhas logo antes dos comandos que mudam o valor desse vetor e em nenhum momento depois do vetmenor[] assumir os valores vetmenor[]=[ 0, 1, 1], esses System.out.println foram acionados. Logo não tem como o vetmenor ter mudado de vetmenor[]=[ 0, 1, 1] para vetmenor[]=[ 1, 1, 1]. Porém isso aconteceu. Talvez eu não tenha marcado todos os momentos em que o vetmenor[] muda de valor com System.out.println(), já que isso está acontecendo. E todos os momentos em que se muda o valor de vetmenor[] que eu achei estão na função caminho(). Tenho quase toda certeza que a função verificar() não está influenciando nisso, pois está certa.
Os System.out.println que coloquei nos momentos que o vetmenor[] muda de valor são:
System.out.println(“Menor=”+menor);
System.out.println(“Entrou no menor!!@!”);
O código está lá em baixo, mas está mal organizado:
Vou tentar dar uma resumida nas coisas mais importantes:
conty é para mostrar quando é a primeira vez que o programa acha uma combinação válida.
conty=0 quer dizer que ainda o programa não achou nada válido.
conty=2 quer dizer que o programa achou pela primeira vez uma combinação válida.
vet2[] é para determinar quais caminhos diretos entre duas vilas é para o programa escolher para usar em suas combinações.
vet2[i]=0, significa que o caminho i, ou seja, o caminho vet[i][] não é para ser utilizado.
vet2[i]=1, significa que o caminho i, ou seja, o caminho vet[i][] é para ser utilizado.
vetmenor[] é o vetor que armazena o vet2[] que causa menos danos ambientais.
vet[][] representa todos os caminhos disponíveis para uso.
import java.util.Scanner;
public class Redotica {
static Scanner leitor=new Scanner(System.in);
static int n, m, permg, menor, vetmenor[],conty;
public static void main(String[] args) {
// TODO Auto-generated method stub
conty=0;
test(1);
}
public static void test(int num) {
int n2,m2, vetmenor2[];
n2=leitor.nextInt();
m2=leitor.nextInt();
m=m2;
n=n2;
if(n2!=0) {
int vet2[]=new int[m2];
int vet[][]=new int[m2][3];
for(int i=0;i<m2;i++) {
vet[i][0]=leitor.nextInt();
vet[i][1]=leitor.nextInt();
vet[i][2]=leitor.nextInt();
}
vetmenor2=new int[m2];
conty=0;
caminho(vet, 0, vet2);
vetmenor2=vetmenor;
//test(num+1);
System.out.println("Teste "+num+ " Menor: "+menor);
for(int i2=0;i2<m2;i2++) {
if(vetmenor2[i2]==1) {
System.out.print(vet[i2][0]+" "+vet[i2][1]);
System.out.println("");
}
}
}else {
}
}
public static void caminho(int vet[][], int i, int vet2[]) {
if(i<m) {
vet2[i]=0;
caminho(vet, i+1, vet2);
vet2[i]=1;
caminho(vet, i+1, vet2);
}else {
int cid;
int vetcid[]=new int[n];
int cont2=0;
for(cid=2;cid<=n;cid++) {
for(int i2=1;i2<n;i2++) {
vetcid[i2]=0;
}
vetcid[0]=1;
verificar(vet, vetcid, cid, 1, 0, vet2);
if(permg==1) {
cont2++;
}
}
if(cont2==n-1) {
System.out.println("Entro permg");
int desastre=0;
for(int i2=0;i2<m;i2++) {
if(vet2[i2]==1) {
desastre=desastre+vet[i2][2];
}
}
System.out.println("Conty="+conty);
if(conty==0) {
//momento que vetmenor[] muda de valor
menor=desastre;
vetmenor=vet2;
conty=2;
System.out.println("Menor="+menor);
for(int i2=0;i2<m;i2++) {
if(vetmenor[i2]==1) {
System.out.print(vet[i2][0]+" "+vet[i2][1]);
System.out.println("");
}
}
}else
if(desastre<menor) {
//momento que vetmenor[] muda de valor
System.out.println("Entrou no menor!!@!");
menor=desastre;
vetmenor=vet2;
System.out.println("Menor="+menor);
for(int i2=0;i2<m;i2++) {
if(vetmenor[i2]==1) {
System.out.print(vet[i2][0]+" "+vet[i2][1]);
System.out.println("");
}
}
}
}
}
}
public static void verificar(int vet[][], int vetcid[],int cid, int cidatual,int cont, int vet2[]) {
int i=0;
permg=0;
while((i<m)&&(permg==0)) {
if((cidatual==vet[i][0])&&(vet2[i]==1)) {
int i2=0;
int perm=0;
while((perm==0)&&(i2<n)) {
if(vetcid[i2]==vet[i][1]) {
perm=1;
}
i2++;
}
if(perm==0) {
if(vet[i][1]==cid) {
permg=1;
}else {
vetcid[cont]=vet[i][1];
verificar(vet, vetcid, cid, vet[i][1], cont+1, vet2);
}
}
}else if((cidatual==vet[i][1])&&(vet2[i]==1)){
int i2=0;
int perm=0;
while((perm==0)&&(i2<n)) {
if(vetcid[i2]==vet[i][0]) {
perm=1;
}
i2++;
}
if(perm==0) {
if(vet[i][0]==cid) {
permg=1;
}else {
vetcid[cont]=vet[i][0];
verificar(vet, vetcid, cid, vet[i][0], cont+1, vet2);
}
}
}
i++;
}
}
}
Se vocês executarem o programa com os mesmos valores do teste que citei lá em cima, o programa vai retornar isso:
Entro permg
Conty=0
Menor=20
2 3
3 1
Entro permg
Conty=2
Entro permg
Conty=2
Entro permg
Conty=2
Teste 1 Menor: 20
1 2
2 3
3 1
O resultado final é as 4 ultimas linhas.
O estranho é que o valor do menor está certo, mas a combinação não e o programa em um dado momento achar a combinação que eu queria, mas logo muda. A questão é que eu não sei o como o vetmenor[] está mudando de valor sendo que os System.out.println que eu coloquei nos momentos em que o vetmenor[] muda de valor não estão sendo acionados, talvez eu tenha esquecido de algum outro lugar do código que o vetmenor[] mudar, mas acredito que não seja isso.
E a combinação vet2[ 1, 1, 1], que é a errada, é a ultima combinação a ser analisada pelo programa.