Buonasera a tutti,
Sto tentando di risolvere il problema in oggetto. Ho già letto che qualcuno ha proposto di risolverlo usando l’induzione, ma sinceramente, pur trovandola una possibilità interessante, non sono riuscito ad applicarla.
A una prima occhiata (non sono molto esperto però) sembrerebbe un qualcosa di simile ad un indipendent set, però è un grafo orientato e bidirezionato. Prima domanda: esiste un algoritmo che consente di applicare il vertex cover ad un grafo bidirezionato?
Capendo da subito che non sarei riuscito a implementare una cosa del genere, ho tentato un approccio diverso. Per ogni nodo ho costruito due vector che contengono tutte le squadre che lo hanno battuto e tutte quelle che ha battuto. Poi ho cercato almeno di consegnare delle soluzioni parziali e ci sono riuscito.
Sono arrivato ad una soluzione da 53.33 punti che dà dal test 001 al test 006 risposte corrette, per tutti gli altri test dà soluzioni parziali. In realtà all’inizio mi dava risposta mancante nel test 1 e nel 4, ma ho capito che bastava scrivere nel file di output un nodo qualsiasi perché la soluzione era un gruppo di un elemento.
Il mio algoritmo, scorrendo i nodi da 1 a N, verifica se qualche nodo già presente nella soluzione batte il nodo i scorrendo gli archi inversi. Se questo si verifica, elimina il nodo già presente nella soluzione. Se scorrendo gli archi inversi di un altro livello trovo qualche nodo già presente in soluzione non aggiungo il nodo i, altrimenti sì. Poi elimino tutti gli eventuali nodi battuti dal nodo i già presenti in soluzione.
Seconda domanda: l’algoritmo non è molto ortodosso, ma già che mi ha portato ad avere delle soluzioni parziali, se io costruissi prima un vettore statico che conta quanti nodi “coprono” il nodo i e lo incrementassi ogni volta che una cosa del genere si verifica, diminuendolo quando uno di questi nodi viene tolto dalla soluzione, e poi verificassi quanti elementi di questo vettore statico hanno valore 0 e li coprissi in un secondo momento, quanto mi avvicinerei alla soluzione completa? per l’algoritmo che ho scritto finora il tempo peggiore è 0,6 su 3 secondi di TL, potrei riuscire a fare questa modifica entro 2,4 secondi?
Grazie in anticipo
EDIT: 0,6 era il tempo peggiore utilizzando cin e cout, usando scanf e printf si dimezza. Dovrebbe cambiare poco
e va beh, domani sarò a Catania e chiederò a chiunque incontro se ha risolto questo problema