Esercizi sulle olimpiadi informatica (superiori)

I seguenti esercizi riguardano Olimpiadi Informatica studiati nella Lezione 21 della Parte Prima. Essi sono divisi per paragrafi in modo tale da favorire la scelta degli esercizi specifici.

Sunnydale

Sunnydale (sunny)

Difficoltà D = 2

Il problema

Sunnydale è una città che - per ragioni storiche e ambientali - ospita un elevatissimo numero di vampiri.

Per ragioni cutanee i vampiri non possono sopportare la luce solare e, storicamente, hanno sempre avuto enormi difficoltà a viaggiare col sole alto nel cielo; l’attraversamento delle gallerie sotterranee di Sunnydale è sempre stato il mezzo preferito dai vampiri per muoversi nella città.

I continui crolli delle gallerie hanno creato dei fori nei soffitti, rendendone alcune troppo luminose per un attraversamento tranquillo e sereno.

Harmony, una ragazza-vampiro, passeggia per le gallerie di Sunnydale quando il suo amico Spike le telefona per invitarla a casa sua.

Purtroppo ella si muove per le gallerie sotterranee secondo una regola tanto semplice quanto tassativa: ad ogni svincolo sceglie sempre e comunque la galleria meno luminosa per paura di rovinare la propria pelle.

Sapendo che non esistono due gallerie egualmente luminose, bisogna determinare se Harmony possa raggiungere la casa sotterranea di Spike e, in caso affermativo, quante gallerie le sono necessarie per arrivare.

Dati di input

La prima riga del file input.txt è composta da quattro numeri interi N, M, H e S: il primo rappresenta il numero degli svincoli (numerati da 1 a N), il secondo rappresenta il numero delle gallerie, il terzo rappresenta l’indice dello svincolo in cui si trova Harmony quando riceve la telefonata; il quarto, infine, rappresenta l’indice dello svincolo della casa di Spike.

Ognuna delle successive M righe descrive una galleria e contiene tre numeri interi A, B e L separati da uno spazio: i primi due rappresentano gli svincoli collegati dalla galleria mentre il terzo rappresenta il suo grado di luminosità.

Dati di output

Il file output.txt dovrà contenere un unico numero intero: -1 se Harmony non riuscirà a raggiungere Spike; altrimenti, il numero di gallerie che ella percorrerà prima di raggiungerlo.

Assunzioni

• 2 ≤ N ≤ 50000
• 1 ≤ M ≤ 50000
• Non esistono due gallerie con la stessa luminosità L
• Per ogni galleria, 1 ≤ L ≤ M
• 1 ≤ H, S ≤ N

Esempi di input/output

File input.txt File output.txt

5 6 1 5 -------- 2

1 2 5

2 3 1

3 4 3

4 5 2

5 1 6

1 4 4

File input.txt File output.txt

3 2 2 -------- -1

3 1 2

2 3 1

I grafi

Prima di passare alla risoluzione del problema, si deve prendere in esame la struttura del grafo. In questo caso il grafo si abbina bene al programma che andiamo ad affrontare.

Per grafo si intende una struttura definita da il numero di nodi N e il numero di archi A che si vengono a delineare tra ogni nodo.

Dalla rappresentazione possiamo notare la presenza di 5 nodi e 6 archi

Esempi di problemi del mondo reale che possono essere rappresentati attraverso i grafi sono:

• una carta stradale, dove i nodi sono le città e gli archi sono le strade che li uniscono. Un problema tipico che si vuole risolvere è quello di trovare la minima distanza tra due determinate città;

• un insieme di attività da eseguire in un certo ordine per raggiungere uno scopo, dove le attività sono i nodi e le relazioni di precedenza tra le attività sono gli archi del grafo. In questo caso un problema è quello di stabilire quali sono le attività critiche, cioè quelle che se subiscono un ritardo fanno ritardare l’intera fine del progetto;

• la rete elettrica nazionale, dove i vertici sono le centrali elettriche e gli archi sono le linee ad alta tensione che le collegano. Qua un problema tipico è di stabilire cosa succede al carico della rete quando una linea viene interrotta.

Come si può vedere da questo piccolo insieme di esempi i campi dove trova applicazione la teoria dei grafi sono i più disparati e i problemi che è in grado di risolvere sono di vario genere.

Soluzione

Come si può notare dalla lettura del testo gli elementi per considerare l’utilizzo di un grafo ci sono tutti: gli svincoli che possono essere interpretati come nodi e le gallerie che sono gli archi, ognuna delle quali ha una diversa luminosità. Vi sono inoltre il nodo di partenza (Harmony) e un nodo di arrivo (Spike). Bisogna notare che c’è una condizione che semplifica drasticamente il problema: ad ogni svincolo Harmony sceglie sempre la galleria meno luminosa (e tutte le gallerie hanno luminosità diversa). Questo vuol dire che già quando viene letto l’input sarà possibile eliminare tutte le gallerie che non soddisfano questa condizione e quindi ci si ritroverà con un grafo in cui ogni nodo ha al massimo un arco uscente e quindi per la sua rappresentazione sarà necessario un vettore contenente per ogni nodo l’indice dell’unico nodo raggiungibile e la luce che illumina questa galleria. A questo punto basta semplicemente spostarsi da un nodo all’altro, partendo dal nodo di Harmony e seguendo per ogni nodo l’unico arco uscente. Solo due condizioni sono possibili:

• arrivo al nodo di Spike e con un contatore posso tenere traccia del numero di gallerie attraversate;

• ripasso su di un nodo che ho già attraversato e quindi entro in un ciclo che non mi permetterà di raggiungere mai Spike.

Inizializziamo la luminosità di ogni galleria a infinito (INT_MAX) e segniamo con false le gallerie non visitate, così quando passeremo per un arco potremmo capire se ci siamo già passati oppure no, al fine di non entrare in circuito chiuso.

Possiamo costruire una tabella individuando i percorsi più favorevoli per Harmony (una galleria la si può percorrere sia in un senso che in un altro)

P => Nodo di partenza L => Luminosità tra i due nodi

A => Nodo di arrivo V => Galleria se visitata V(vero) altrimenti F(falso)

Dalla tabella notiamo i percorsi più favorevoli per Harmony da ciascun nodo (per esempio dal nodo 1 è più favorevole andare al nodo 4 poiché la galleria ha la luminosità più bassa rispetto alle altre). Andremo a dichiarare un vettore di struct per ogni svincolo/nodo avente come campi: la luce e lo svincolocollegato.

In arancione la luminosità di ciascun arco/galleria tra i due nodi/svincoli

Fatte queste considerazioni il codice risulta così.

#include <iostream>
#include <cstdlib>
#include <limits.h>
using namespace std;

struct svincolo{
	int luce;
	int svincolocollegato;
	bool visitato;
};

int main(int argc, char** argv) 
{  int n, m, s, h;
   cin>>n>>m>>s>>h;
   
   int i;
   svincolo elenco[n];
   
   for(i=1;i<=n;i++)
    {elenco[i].visitato=false;
     elenco[i].luce=INT_MAX;
    }
    
    int a, b, l;
    
    for(i=1;i<=m;i++)
    {cin>>a>>b>>l;
     if(elenco[a].luce>l)
      {elenco[a].luce=l;
       elenco[a].svincolocollegato=b;
      }
     if(elenco[b].luce>l)
      {elenco[b].luce=l;
       elenco[b].svincolocollegato=a;
      }
    }
    int conta=0;
    int posizione=h;
    
    while(posizione!=s && !elenco[posizione].visitato)
    {elenco[posizione].visitato=true;
     conta++;
     posizione=elenco[posizione].svincolocollegato;
    }
    
    if(posizione==s)
     cout<<conta<<endl;
  else
     cout<<"-1"<<endl;
      return 0;
}