Problema "partite di curling"

Aiuto
1

Sto provando a risolvere questo problema, ma non riesco a trovare una strategia ottimale, qualcuno mi potrebbe dare qualche consiglio?

2

Si può vedere il problema come un grafo dove bisogna trovare il cammino massimo.
Ogni partita deve essere vinta da una delle due squadre e si scontrano tutte quindi, se non sbaglio, un cammino che attraversa tutti i nodi dovrebbe esistere sempre.
Il caso peggiore è partire con una dfs dalla squadra che ha perso tutte le partite perchè non si può continuare la visita, poi partire con una dfs dalla squadra che ha vinto solo la partita contro quest’ultima e così via.
Di conseguenza qual’è il “caso ottimo”?

3

Non credo di aver capito :confused: Potrebbe succedere che non esistono squadre che hanno perso/vinto tutte le partite, potresti darmi qualche aiuto in piĂą? :grinning:

4

Non ero stato molto chiaro in effetti, ci riprovo! (io il problema l’ho risolto così, ci potrebbero essere altre soluzioni) :slight_smile: Ogni nodo perdente che appare nella sequenza finale deve essere nella partita immediatamente successiva come vincente. Quindi la vittoria di una squadra a su una squadra b può essere rappresentata come un arco che va dal nodo a al nodo b e la partita successiva sarà da b(come vincente) ad un nodo non ancora visitato ed alla fine tutti gli archi attraversati di volta in volta formeranno la sequenza finale.
Ora rimane solo trovare un cammino che passa per il maggior numero di nodi :smiley:
Volevo provare con una dfs da ogni nodo, ma poi ho visto che c’è un nodo dal quale è sempre ottimo partire, quello che ha il maggior numero di partite vinte. Nel caso non avesse perso partite gli altri cammini non l’avrebbero incluso e invece nel caso ci fossero stati più vincitori significa che hanno perso almeno una partita tutti e quindi da che nodo vincitore si parte è indifferente.
L’ho risolto con una dfs utilizzando la ricorsione e memorizzando il predecessore per ogni nodo.

5

Allora, ho implementato questa dfs, che lancio dal nodo con maggior numero di partite vinte:

int dfs(int nodo,int distanza,int* percorso){
    if(distanza==N-1 && vis[nodo]==0){
    percorso[distanza]=nodo;
    printf("%d",N-1);
    for(int i=0;i<distanza;i++)
       printf("\n%d %d",percorso[i],percorso[i+1]);
      exit(0);
   }
  if(vis[nodo]==0){
    vis[nodo]++;
    percorso[distanza]=nodo;
    int next=G[nodo][0],best=0;
    for(int i=0;i<G[nodo].size();i++)
      if(vis[G[nodo][i]]==0){
        if(best<vinte[G[nodo][i]]){
          best=vinte[G[nodo][i]];
          next=G[nodo][i];
        }
      }
      dfs(next,distanza+1,percorso);
  }
}

Ti spiego il mio ragionamento: se mi conviene partire dal nodo che ha più partite vinte, allora anche tra i figli mi conviene prendere quello più vincente: infatti è come risolvere un sottoproblema di quello iniziale.
Facendo così però totalizzo solo 40/100, infatti a volte non trova un percorso lungo N-1 e non stampa niente. In cosa sbaglio? o capito male qualche cosa?

6

Ok, mi sono appena accorta che dimenticavo di richiamare la funzione cancella, che toglie 1 vittoria ai nodi che hanno vinto contro il nodo eliminato, adesso prendo 100/100 :smile:

1 Mi Piace