Newsgroup: it.comp.lang.c
Titolo: Gara automobilistica

Ciao a tutti.
al seguente indirizzo
http://gongolo.usr.dsi.unimi.it/~vigna/ioi/selezioni/listdir.php?dir=gara;ti
tle=Gara%20automobilistica è presente un file .html dove è descritto un
problema di programmazione proposto qualche anno fa alle olimpiadi nazionali
di informatica. I file contrassegnati con il nome inputn.txt ed outputn.txt
sono esempi di quale file di output ci si aspetta con un determinato file di
input.
Sapreste suggerirmi qualche dritta su come organizzare l'algoritmo di
riosluzione. A me un'idea è venuta in mente però mi pare che richieda troppo
tempo.
Grazie.

ammetto di non aver letto a fondo il problema ma solo a guardare la
figura č evidente che bisogna usare un algoritmo per il cammino minimo
tra due nodi in un grafo.
ce ne sono alcuni, il piů famoso (credo) č quello di dijkstra che
trovi in tutti i libri di algoritmi altrimenti qui:
http://homes.dsi.unimi.it/~goldwurm/Appunti/appu02.ps
trovi delle dispense del corso di algoritmi e strutture dati che
parlano anche di questo algoritmo.
ciao

trovi in tutti i libri di algoritmi
O probabilmente all'interno dello stesso sito dove hai trovato
l'esempio, o almeno l'anno scorso c'era la spiegazione di qualche
algoritmo insieme agli esempi per le IOI.
-- 
Marco Barisione (ICQ 84277092)

tempo.
Ho adattato un programma che avevo scritto qualche tempo fa per
risolvere un quesito analogo.
Funziona (l'ho testato).
Se tu avessi problemi con i file di input e output, prova a
specificare il percorso completo, stando attento a mettere due
backslash (\\) al posto di uno solo.
Viene generata una matrice che contiene le adiacenze con gli altri
nodi (50 nodi quindi una matrice 50 * 50).
La matrice è composta così: la i-esima riga ha "fine" elementi
caricati da file (fine <= DIM), ogni j-esimo indice della riga può
assumere valore 0 oppure 1, 0 significa che il nodo i non può
raggiungere il nodo j, 1 significa invece che c'è un arco che li
collega.
Per la ricerca dei nodi che non si possono togliere, il lavoro viene
svolto da un ciclo for in fondo al main.
Un'apposita funzione (togli) rimuove dalla matrice di adiacenze la
riga e la colonna che riguardano un nodo (equivale a togliere il nodo
dal percorso senza alterare il resto) e ne fa una copia in appositi
vettori. Dopodiché il percorso viene esplorato alla ricerca di una
strada che porti fino alla conclusione. Se questa non esiste, il nodo
viene scritto sul file di output, in quanto è uno dei nodi
indispensabili del circuito (togliendolo non si arriva in fondo).
Infine viene ripristinato il nodo rimosso e il ciclo continua fino
alla fine.
La funzione di esplorazione è semplicemente una visita in profondità
del percorso: avanza fino ad incontrare un vicolo cieco, oppure finché
non si ritrova in un nodo già visitato; quando trova un ostacolo del
genere, torna indietro fino al nodo più vicino tra quelli visitati,
che permetta altre scelte. Si ferma solamente quando esaurisce tutte
le possibilità, oppure quando trova un percorso valido.
Un vettore globale (path) contiene il percorso tracciato durante la
ricorsione dalla funzione percorri. Per ogni chiamata la funzione
percorri controlla che path non contenga già una volta il nodo che si
sta percorrendo (per evitare loop infiniti), e se lo contiene, ritorna
indietro, altrimenti lo aggiunge al percorso e prosegue.
#include <stdio.h>
#define DIM 50
#define INFILE "input.txt"
#define OUTFILE "output.txt"
char adiacenze[DIM][DIM]; /* matrice delle adiacenze */
char temp_riga[DIM];      /* vettore per memorizzare la riga
temporaneamente tolta */
char temp_colonna[DIM];   /* come sopra per la colonna */
char fine;                /* per sapere dove fermarsi */
char path[DIM];          /* vettore del percorso seguito nella
ricorsione */
void togli(char);
void ripristina(char);
char percorri(char, char);
int main(void)
{
  char i, j;
  int temp;
  FILE *miofile;
 
  for(i = 0; i < DIM; i++)    /* inizializza la matrice delle
adiacenze */
    for(j = 0; j < DIM; j++)
      adiacenze[i][j] = 0;
 
  miofile = fopen(INFILE, "rt"); /* <- "rt" senno' Laforgia si offende
;-) */
  if(miofile == NULL)
    return 1;   /* se non riesce ad aprire il file, esce */
 
  fine = 0;
 
  do      /* legge dal file e riempie la matrice adiacenze */
  {
    if(fscanf(miofile, "%d", &temp) == EOF) /* se il file finisce
*/
    {                                       /* prematuramente, da'
errore */
      temp = -1;                            /* (viene intercettato
dopo)  */
      fine = DIM;
    }
    else  /* altrimenti riempie la matrice delle adiacenze */
    {
      if(temp > 0)                 /* se c'e' un arco... */
        adiacenze[fine][temp] = 1;  /* ... lo attiva. */
      else  /* se il nodo e' completato, passa al seguente (riga
succ.) */
        fine++;
    }
  }while(fine < DIM && temp != -1);
 
  fclose(miofile);
 
  if(fine == DIM && temp != -1)/* se si è verificato un errore, esce
*/
    return 1;                  /* questo intercetta anche file con un
*/
                               /* errato numero di vertici (superiore
a DIM) */
 
  miofile = fopen(OUTFILE, "wt");
  if(miofile == NULL)
    return 1;
  for(i = 0; i < fine; i++)     /* controlla tutti i nodi da 1 a DIM-1
*/
  {
    togli(i);    /* rimuove tutti gli archi che collegano il vertice i
*/
    j = percorri(0, 0); /* cerca un percorso dalla partenza all'arrivo
*/
    if(!j)           /* se non esiste percorso, allora il nodo j e'
punto di articolazione... */
      fprintf(miofile, "%d ", i); /* ... quindi lo aggiunge al file di
output. */
    ripristina(i);  /* ripristina il grafo */
  }
 
  fclose(miofile);
  return 0;
}
void togli(char i)   /* sgancia il vertice i dal grafo, ma lo copia in
temp_riga, temp_colonna */
{
  char j;
  for(j = 0; j < fine; j ++)
  {
    temp_riga[j] = adiacenze[i][j]; /* stessa cosa con la colonna */
    adiacenze[i][j] = 0;
    temp_colonna[j] = adiacenze[j][i]; /* stessa cosa con la colonna
*/
    adiacenze[j][i] = 0;
  }
}
void ripristina(char i)   /* ripristina il grafo riconnettendo il
vertice salvato */
{
  char j;
  for(j = 0; j < fine; j ++)
  {
    adiacenze[i][j] = temp_riga[j];
    adiacenze[j][i] = temp_colonna[j];
  }
}
char percorri(char vertice, char depth) /* e' un'esplorazione in
profondita', in pratica */
{
  char i;
  char risultato;
 
  if(vertice == fine - 1)   /* se la ricerca e' finita, restituisce 1
*/
    return 1;
 
  for(i = 0; i < depth; i++)   /* se incontra un ciclo, torna sui suoi
passi */
    if(path[i] == vertice)
      return 0;
 
  path[depth] = vertice;       /* altrimenti segna il percorso */
 
  for(i = 0; i < fine; i++)
    if(adiacenze[vertice][i])   /* se c'e' un arco che collega il
vertice... */
    {
      risultato = percorri(i, depth + 1);  /* ... lo percorre. */
      if(risultato)         /* se il percorso porta alla fine... */
        return risultato;   /* restituisce 1 */
    }
  return 0;    /* se tutte le strade percorse a partire da qui non
arrivano, */
               /* restituisce 0 */
}