primero asi seria la entrada:
6 2 3
noria 12
mon_rusa 20
carritosCHO 100
silla_voladora 15
gusanito 1
casa_terror 13
0 1
2 1
0 2
y la salida es:
CarritosCho Mon_rusa
POSIBLE
Entrada CarritosCho Mon_rusa Entrada
Entrada Mon_rusa CarritosCho Entrada
si es imposible solo devuelve imposible
pero aparte el programa no me compila y no se si el backtracking este bien, por favor podrian ayudarme .
hola podrian ayudarme con este codigo, es un backtracking que me tiene que devolver si es posible o es imposible que haya circuito hamiltoniano
Código
#include <iostream> #include <string> using namespace std; class atraccion { private: int x; string name; public: atraccion () {} atraccion (int var, string nnombre){ x=var; name = nnombre; } ~atraccion() {} void set_x (int val) { //modifica el x x = val; } int get_x () { //devuelve el x return x; } void set_name ( string nom) { //modifica el nombre name =nom; } string get_name () { //devuelve el nombre return name; } }; void back (int i, int j, bool array[11][11],int camino[],int acum=0 , int arist){ if((j==0) && (acum= arist-1)){ cout<<"POSIBLE"<<endl; }else{ if (array[i][j] == true ){ for (int x=0;x<11;x++){ int p=j; camino[x]=j; array[i][j] = array[j][i]=false; acum=acum+1; back (i=p, j=0, array, camino, acum, arist); camino[x] = ' '; //desmarco y deshago mu solucion acum= acum-1; //desmarco y deshago mi solucion } }else{ back(i,j++,array,camino, acum,arist); //busco otra solucion } cout<< "IMPOSIBLE"<<endl; } } int main (){ int m, n, h,div; int posmayor,mayor; bool mat[11][11]; int x,y; string nombre; atraccion intercambio; int r=0,s=0,t=0; cin>>m>>n>>h; int sol[h-1]; atraccion ar [m]; //arreglo que almacena cada atraccion for (int i=0;i<m;i++) { cin>>nombre; cin>>div; ar[i].set_name(nombre); ar[i].set_x (div); } for( int g=0;g<11;g++){ //matriz de adyacencia for (int f=0;f<11;f++){ mat[g][f] =false; } } for (int d=0;d<=h-1;d++){ // Coloco de par en par de vértices conexos hasta que no haya más aristas cin >> x >> y; // Leo la pareja mat[x][y]=mat[y][x]=true; // Guardo el dato en la matriz de adyacencia } for (int w=0;w<=m-2;w++){ //ordenamiento //modelo 2 posmayor = w; mayor = ar[w].get_x(); for (int k=w+1; k<=m-1; k++){ /*if ((ar[k].get_x() == mayor) && (ar[k].get_name () < ar[w].get_name())){ mayor= ar[k]; posmayor=k; }else{*/ if (ar[k].get_x() > mayor) { mayor = ar[k].get_x(); posmayor =k; } //} } intercambio = ar[posmayor]; //se encarga de cambiarlos ar[posmayor] =ar[w]; ar[w] = intercambio; } for (int j=0;j<n;j++) { //imprime populares cout<<ar[j].get_name()<<endl; } for (int u=0;u<11;u++) { //imprime booleana for(int v=0;v<11;v++){ cout<<mat[u][v]; } } back(r, s, mat, sol, t , n); return 0; }