Server#10456

Server (Həll təhlili)

Qraf $1 0^{4}$ 10^4-dək təpəyə və $4 \cdot 1 0^{4}$ 4 \cdot 10^4-dək tilə malikdir, ona görə də onu qonşuluq siyahısı şəklində saxlayacağıq. Bütün tillərin çəkiləri müsbətdir, deməli, ən qısa məsafələri Dijkstra alqoritmi ilə tapmaq olar.

Məsələnin qraf terminləri ilə ifadəsi. $a$ və $b$ təpələri arasındakı ən qısa yolun uzunluğunu $d (a, b)$ ilə işarə edək. Əgər server $v$ şəhərində yerləşirsə, $c_{i}$ c_i şəhərindən olan qonaq $d (c_{i}, v)$ d(c_i, v) gecikməsini alır. Bütün qonaqların ümumi gecikməsi bərabərdir

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)

$S (v)$ qiyməti minimal olan $v$ təpəsini tapmaq lazımdır, bərabərlik halında isə — nömrəsi ən kiçik olanı.

Niyə Dijkstranı qonaqların şəhərlərindən işə salırıq. Hər bir namizəd-təpə $v$ üçün $v$ -dən Dijkstra alqoritmini işə salıb qonaqların $k$ şəhərinə olan məsafələri toplamaq olardı. Lakin namizədlərin sayı $1 0^{4}$ 10^4-dək ola bilər, bu qədər işə salma çox həddən artıqdır. Qeyd edək ki, qraf istiqamətsizdir, ona görə $d (c_{i}, v) = d (v, c_{i})$ d(c_i, v) = d(v, c_i). Deməli, qonaq $c_{i}$ c_i-nin şəhərindən Dijkstranın bir dəfə işə salınması dərhal serverin bütün mümkün yerləşdirilmə yerləri üçün bu qonağın gecikməsini verir. Qonaqların sayı $100$ -dən çox olmadığına görə, $k$ dəfə işə salmaq kifayətdir.

Cəm necə yığılır. İlkin olaraq sıfırlarla doldurulmuş $s u m [1.. n]$ massivi yaradaq. $s u m [v]$ elementi server $v$ təpəsində yerləşdirildikdə qonaqların ümumi gecikməsini saxlayacaq.

Sonra hər bir qonaq üçün növbə ilə:

$c_{i}$ c_i təpəsindən Dijkstra alqoritmini işə salırıq və $d i s t [1.. n]$ dist[1..n] massivini alırıq, burada $d i s t [v] = d (c_{i}, v)$ dist[v] = d(c_i, v). Bu, server $v$ şəhərində yerləşdikdə $i$ -ci qonağın gecikməsidir.
Bütün $v = 1, 2, ..., n$ v = 1, 2, ..., n təpələrini gəzirik və $s u m [v] + = d i s t [v]$ sum[v] += dist[v] əməliyyatını icra edirik. Beləliklə, $i$ -ci qonağın töhfəsini serverin hər bir mümkün yerləşdirilmə yerinin ümumi gecikməsinə əlavə edirik.

Bütün $k$ qonaq emal edildikdən sonra hər bir $s u m [v]$ elementi düz $k$ toplanan — $v$ təpəsinə qədər bütün qonaqların gecikmələrini ehtiva edir, yəni $s u m [v] = S (v)$ sum[v] = S(v).

Cavabın seçilməsi. $v = 1, 2, ..., n$ v = 1, 2, ..., n təpələrini nömrələrin artma qaydasında gəzirik və minimal cəmə malik təpəni yadda saxlayırıq. Cavabı yalnız sərt bərabərsizlik $s u m [v] < b es t$ sum[v] < best olduqda yeniləyirik. Bu zaman eyni minimal cəmə malik bir neçə təpə olduqda onlardan birincisi, yəni ən kiçik nömrəli olan qalır.

Minimum yalnız qonaqların şəhərləri arasında deyil, bütün $n$ təpə arasında axtarılır: optimal yer qonağı olmayan şəhər ola bilər.

Misal

Misalda verilmiş qraf aşağıdakı şəkildədir:

Qonaqların yaşadığı təpələrdən — $1, 2$ və $5$ — Dijkstra alqoritmini işə salaq. Bu təpələrin hər biri üçün bütün digər şəhərlərə qədər ən qısa məsafələri müəyyən edək.

Sonra qrafın hər bir təpəsi üçün qonaqları olan bütün şəhərlərə qədər olan məsafələrin cəmini tapaq. Məsafələrin minimal cəmi $13$ -ə bərabərdir və o, ən kiçik $2$ nömrəli təpədə əldə edilir.

Beləliklə, server $2$ nömrəli şəhərdə yerləşdirilməlidir. Ondan qonaqların yaşadığı şəhərlərə qədər ümumi məsafə $5 + 0 + 8 = 13$ 5 + 0 + 8 = 13 təşkil edir.

Alqoritmin reallaşdırılması

Sonsuzluq sabitini elan edək.

#define INF 0x3F3F3F3F

$e d g e$ strukturu til haqqında məlumatı saxlayacaq: tilin apardığı $n o d e$ təpəsini və bu tilin $d i s t$ çəkisini.

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

$(n o d e, d i s t)$ (node, dist) cütlərini $d i s t$ qiymətinin azalması üzrə sıralamaq üçün komparator elan edək.

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

Qrafı təqdim etmək üçün qonşuluq siyahısı elan edək.

vector<vector<edge> > g;

Dijkstra funksiyası Dijkstra alqoritmini reallaşdırır. O, giriş olaraq $g$ qrafını və başlanğıc $s t a r t$ təpəsini qəbul edir. Qaytarılan qiymət $d$ massividir, burada $d [i]$ $s t a r t$ təpəsindən $i$ təpəsinə qədər ən qısa məsafəni saxlayır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Giriş çəkili qrafını oxuyuruq.

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++

Qonaqların yaşadığı şəhərlərdən Dijkstra alqoritmini işə salırıq.

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++

Bu anda $d p [i]$ $i$ təpəsindən qonaqların yerləşdiyi bütün şəhərlərə qədər ən qısa məsafələrin cəmini saxlayır. $d p$ massivinin elementləri arasında minimal qiyməti tapmaq və müvafiq cavabı çıxarmaq qalır. $pt r$ dəyişəni serverin yerləşdirilməli olduğu ən kiçik nömrəli təpəni saxlayır.

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

C++

Cavabı çıxarırıq.

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