Server#10456

Server (Editoriale)

Il grafo contiene fino a $1 0^{4}$ 10^4 vertici e fino a $4 \cdot 1 0^{4}$ 4 \cdot 10^4 archi, quindi lo memorizzeremo sotto forma di lista di adiacenza. Tutti i pesi degli archi sono positivi, quindi le distanze minime possono essere trovate con l'algoritmo di Dijkstra.

Formulazione del problema in termini di grafo. Indichiamo con $d (a, b)$ la lunghezza del cammino minimo tra i vertici $a$ e $b$ . Se il server si trova nella città $v$ , l'ospite della città $c_{i}$ c_i ottiene un ritardo $d (c_{i}, v)$ d(c_i, v). Il ritardo totale di tutti gli ospiti è uguale a

S (v) = d (c_{1}, v) + d (c_{2}, v) + ... + d (c_{k}, v)

S(v) = d(c_1, v) + d(c_2, v) + ... + d(c_k, v)

Bisogna trovare il vertice $v$ con il valore minimo di $S (v)$ , e in caso di parità — con il numero più piccolo.

Perché avviamo Dijkstra dalle città degli ospiti. Si potrebbe, per ogni vertice candidato $v$ , eseguire Dijkstra a partire da $v$ e sommare le distanze verso i $k$ città degli ospiti. Ma i candidati sono fino a $1 0^{4}$ 10^4, e un numero così elevato di esecuzioni è eccessivo. Notiamo che il grafo non è orientato, quindi $d (c_{i}, v) = d (v, c_{i})$ d(c_i, v) = d(v, c_i). Ciò significa che una singola esecuzione di Dijkstra dalla città dell'ospite $c_{i}$ c_i fornisce immediatamente il ritardo di questo ospite per tutti i possibili luoghi in cui collocare il server. Gli ospiti non sono più di $100$ , quindi bastano $k$ esecuzioni.

Come si accumula la somma. Creiamo un array $s u m [1.. n]$ , inizialmente riempito di zeri. L'elemento $s u m [v]$ conterrà il ritardo totale degli ospiti nel caso in cui il server sia collocato nel vertice $v$ .

Poi, per ciascun ospite, a turno:

Eseguiamo l'algoritmo di Dijkstra a partire dal vertice $c_{i}$ c_i e otteniamo l'array $d i s t [1.. n]$ dist[1..n], dove $d i s t [v] = d (c_{i}, v)$ dist[v] = d(c_i, v). Questo è il ritardo dell' $i$ -esimo ospite se il server si trova nella città $v$ .
Scorriamo tutti i vertici $v = 1, 2, ..., n$ v = 1, 2, ..., n ed eseguiamo $s u m [v] + = d i s t [v]$ sum[v] += dist[v]. Così aggiungiamo il contributo dell' $i$ -esimo ospite al ritardo totale per ogni possibile posizione del server.

Dopo aver elaborato tutti i $k$ ospiti, ogni elemento $s u m [v]$ contiene esattamente $k$ addendi — i ritardi di tutti gli ospiti verso il vertice $v$ , cioè $s u m [v] = S (v)$ sum[v] = S(v).

Scelta della risposta. Esaminiamo i vertici $v = 1, 2, ..., n$ v = 1, 2, ..., n in ordine crescente di numero e memorizziamo il vertice con la somma minima. Aggiorniamo la risposta solo in caso di disuguaglianza stretta $s u m [v] < b es t$ sum[v] < best. In questo modo, se più vertici hanno la stessa somma minima, resterà il primo di essi, cioè quello con il numero più piccolo.

Il minimo viene cercato su tutti gli $n$ vertici, e non solo sulle città degli ospiti: il luogo ottimale potrebbe essere una città in cui non ci sono ospiti.

Esempio

Il grafo riportato nell'esempio ha il seguente aspetto:

Eseguiamo l'algoritmo di Dijkstra a partire dai vertici in cui risiedono gli ospiti: $1, 2$ e $5$ . Per ciascuno di questi vertici determiniamo le distanze minime verso tutte le altre città.

Poi, per ciascun vertice del grafo, troviamo la somma delle distanze verso tutte le città con ospiti. La somma minima delle distanze è uguale a $13$ , ed è raggiunta nel vertice con il numero più piccolo $2$ .

Quindi, il server dovrebbe essere collocato nella città $2$ . La distanza totale da esso verso le città in cui risiedono gli ospiti è pari a $5 + 0 + 8 = 13$ 5 + 0 + 8 = 13.

Implementazione dell'algoritmo

Dichiariamo la costante infinito.

#define INF 0x3F3F3F3F

La struttura $e d g e$ memorizzerà le informazioni su un arco: il vertice $n o d e$ a cui conduce l'arco, e il peso $d i s t$ di tale arco.

struct edge
{
  int node, dist;
  edge(int node, int dist) : node(node), dist(dist) {}
};

Dichiariamo un comparatore per ordinare le coppie $(n o d e, d i s t)$ (node, dist) in ordine decrescente del valore $d i s t$ .

bool operator< (edge a, edge b)
{
  return a.dist > b.dist;
}

Dichiariamo una lista di adiacenza per rappresentare il grafo.

vector<vector<edge> > g;

La funzione Dijkstra implementa l'algoritmo di Dijkstra. Riceve in ingresso il grafo $g$ e il vertice iniziale $s t a r t$ . Il valore restituito è l'array $d$ , dove $d [i]$ contiene la distanza minima dal vertice $s t a r t$ al vertice $i$ .

void Dijkstra(vector<vector<edge> >& g, vector<int>& d, int start)
{
  priority_queue<edge> pq;
  pq.push(edge(start, 0));

  d = vector<int>(n + 1, INF);
  d[start] = 0;

  while (!pq.empty())
  {
    edge e = pq.top(); pq.pop();
    int v = e.node;

    if (e.dist > d[v]) continue;

    for (auto e : g[v])
    {
      int to = e.node;
      int cost = e.dist;
      if (d[v] + cost < d[to])
      {
        d[to] = d[v] + cost;
        pq.push(edge(to, d[to]));
      }
    }
  }
}

C++

Parte principale del programma. Leggiamo i dati di input.

scanf("%d %d %d", &n, &m, &k);
c.resize(k);
for (i = 0; i < k; i++)
  scanf("%d", &c[i]);

Leggiamo il grafo pesato in input.

g.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d %d", &a, &b, &w);
  g[a].push_back(edge(b, w));
  g[b].push_back(edge(a, w));
}

C++

Eseguiamo l'algoritmo di Dijkstra a partire dalle città in cui risiedono gli ospiti.

dp.resize(n + 1);
for (i = 0; i < k; i++)
{
  Dijkstra(g, dist, c[i]);

  for (j = 1; j <= n; j++)
   dp[j] += dist[j];
}

C++

A questo punto $d p [i]$ contiene la somma delle distanze minime dal vertice $i$ a tutte le città in cui si trovano gli ospiti. Rimane da trovare il valore minimo tra gli elementi dell'array $d p$ e stampare la risposta corrispondente. La variabile $pt r$ memorizza il numero più piccolo del vertice in cui collocare il server.

res = INF;
for (i = 1; i <= n; i++)
{
  if (dp[i] < res)
  {
    res = dp[i];
    ptr = i;
  }
}

C++

Stampiamo la risposta.

printf("%d %d\n", ptr, dp[ptr]);