void check(Graph g, int *sol, int n, TS vnames, int *ok, int *best_sol, float *best_diam){
    int i, j, k = 0, n_archi = (g->V)*(g->V - 1)/2;
    float dim;

    for (i = 0; i < g->V; i++){
        for (j = 0; j < g->V; j++){
            g->archi[i][j] = g->matj[i][j];
        }
    }

    for (i = 0; i < g->V-1; i++){
        for (j = i+1; j < g->V; j++){
            if (sol[k++]){
                g->archi[i][j] = g->archi[j][i] = calcoladist(g, i, j);
            }
        }
    }

    if (GRAPHcc(g) == 1){
        dim = diam (g);
        if (dim < *best_diam){
            *best_diam = dim;
            (*ok) = 1;
            for (i = 0; i < n_archi; i++){
                best_sol[i] = sol[i];
            }
        }
    }
}

void powerset_r (Graph g, int *sol, int *best_sol, float *best_diam, int pos, int n, int start, int *ok, TS vnames){
    int i, n_archi = (g->V)*(g->V - 1)/2;

    if (pos == n){
        check(g, sol, n, vnames, ok, best_sol, best_diam);
        return;
    }

    for (i = start; i < n_archi; i++){
        sol[i] = 0;
        powerset_r(g, sol, best_sol, best_diam, pos+1, n, i+1, ok, vnames);
    }
    return;
}

void risolvicardmin (Graph g, TS vnames){

    int ok = 0, *sol, n, *best_sol, i, j, k = 0;
    float best_diam = (float)INT32_MAX;
    int n_archi = (g->V)*(g->V - 1)/2; //considero l'insieme di archi massimo dato un grafo non orientato

    sol = malloc(n_archi * sizeof(int));
    best_sol = calloc(n_archi, sizeof(int));

    //powerset di archi da aggiungere con terminazione al numero di archi massimo
    for (n = 1; n <= n_archi && ok == 0; n++){

        powerset_r(g, sol, best_sol, &best_diam, 0, n, 0, &ok, vnames);
        if (ok == 1){

            //ho dimenticato di aggiungere la stampa

            for (i = 0; i < n_archi; i++){
                printf("%d ", best_sol[i]);
            }

            printf("\nArchi aggiunti:\n");

            for (i = 0; i < g->V-1; i++){
                for (j = i+1; j < g->V; j++){
                    if (best_sol[k++]){
                        printf("%s - %s\n", TSleggiIndice(vnames, i), TSleggiIndice(vnames, j));
                    }
                }
            }
            printf("Di diametro minimo: %f\n", best_diam);
            return;
        }
    }