Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: territoriali.olinfo.it
Per spegnere una lampadina possiamo abbozzare un semplice algoritmo come il seguente:
Passo 1: controlliamo se la lampadina è collegata ad un interruttore di tipo 1.
Passo 2: se la lampadina è collegata ad un interruttore di tipo 1 allora pigiamo quell'interruttore e abbiamo finito.
Passo 3: se la lampadina non è collegata a nessun interruttore di tipo 1 allora pigiamo un interruttore di tipo 2 e ripetiamo il procedimento sull'altra lampadina connessa a tale interruttore.
Un algoritmo come questo, però, non sempre produce una soluzione ottimale, talvolta richiede di pigiare più interruttori di quelli strettamente necessari. Possiamo però notare che questo algoritmo è molto simile ad una ricerca in profondità (DFS), possiamo quindi provare a sostituire la DFS con una ricerca in ampiezza (BFS) per ottenere la soluzione ottimale.
Rappresentiamo l'impianto elettrico come un grafo in cui ogni nodo rappresenta una lampadina e ogni arco rappresenta un interruttore di tipo 2. Definiamo un nodo speciale se è direttamente connesso ad un interruttore di tipo 1. Per spegnere una lampadina ci basta quindi trovare un percorso semplice fino ad un nodo speciale, per farlo possiamo utilizzare una DFS oppure una BFS, tuttavia solo la BFS ci garantisce di trovare in nodo speciale più vicino.
Per risolvere questo problema ci basta quindi calcolare la distanza minima di ogni nodo dal nodo speciale più vicino eseguendo una BFS per ogni nodo.
Questa soluzione ha una complessità che ci permette di risolvere la maggior parte dei casi di test, tuttavia alcuni casi sono troppo grandi per essere risolti in un tempo ragionevole.
Anziché trovare il percorso da ogni nodo al nodo speciale più vicino, facciamo l'opposto. Partiamo dai nodi speciale e cerchiamo il nodo più lontano. Dobbiamo fare però attenzione ad ignorare i nodi già raggiungi con un percorso più breve da ottenuto partendo da un altro nodo speciale.
In questo modo possiamo modificare l'algoritmo classico della BFS per risolvere il problema in modo più efficiente! Invece di eseguire una BFS da ogni nodo speciale, eseguiamo un'unica BFS da tutti i nodi speciali contemporaneamente, per farlo ci basta inserire in coda all'inizio dell'algoritmo tutti i nodi speciali anziché uno solo, al termine basta semplicemente stampare il nodo più lontano e la sua distanza dal nodo speciale.
Con questa ottimizzazione la complessità viene ridotta a riuscendo a risolvere molto velocemente anche i casi più grandi e a totalizzare il punteggio pieno.
constexpr int MAXN = 1 << 17, INF = 1e9;
vector<int> grafo[MAXN];
int dist[MAXN];
bool vis[MAXN];
void solve(int t) {
int N, A, B;
cin >> N >> A >> B;
for (int i = 0; i < N; i++) {
grafo[i].clear();
dist[i] = INF;
vis[i] = false;
}
queue<int> Q;
for (int i = 0; i < A; i++) {
int x;
cin >> x;
dist[x] = 1;
Q.push(x);
}
for (int i = 0; i < B; i++) {
int x, y;
cin >> x >> y;
grafo[x].push_back(y);
grafo[y].push_back(x);
}
int ans = 0;
while (!Q.empty()) {
int v = Q.front();
Q.pop();
if (vis[v]) continue;
vis[v] = true;
ans = v;
for (int i : grafo[v]) {
dist[i] = min(dist[i], dist[v] + 1);
Q.push(i);
}
}
cout << "Case #" << t << ": " << ans << " " << dist[ans] << "\n";
}