Tənha Ada#9044

Tənha Ada (Həll təhlili)

Məsələnin şərtinə əsasən, bir adadan çıxdıqdan sonra siz bir daha oraya qayıda bilməzsiniz. Deməli, təpələri adalar, kənarları isə körpülər olan qraf yönlü asiklik qrafdır. Siz yalnız çıxış körpüsü olmayan $v$ adasında, yəni çıxış dərəcəsi sıfır olan dalan təpədə ilişib qala bilərsiniz: $O u t D e g r ee [v] = 0$ OutDegree[v] = 0.

$p r o b [v]$ prob[v] ilə gəzinti zamanı $v$ təpəsinə çatma ehtimalını işarə edək. Başlanğıc təpə üçün $p r o b [r] = 1$ prob[r] = 1; bütün digər təpələr üçün ilkin olaraq $p r o b [v] = 0$ prob[v] = 0. Qrafda dövrələr olmadığından, hər təpəyə ən çoxu bir dəfə baş çəkmək olar.

Tutaq ki, $u$ təpəsindən $O u t D e g r ee [u]$ OutDegree[u] kənar çıxır. $u$ -da olarkən biz onlardan birini bərabər ehtimalla seçirik, deməli $u \to v$ u \to v kənarı ilə $p r o b [u] / O u t D e g r ee [u]$ prob[u] / OutDegree[u] ehtimalla hərəkət edirik. $v$ təpəsinə yalnız onun birbaşa sələflərindən çatmaq olar. Buna görə $p r o b [v]$ prob[v] $v$ -yə daxil olan bütün $u \to v$ u \to v kənarlarının töhfələrinin cəminə bərabərdir:

p r o b [v] = u \to v \sum p r o b [u] / O u t D e g r ee [u]

prob[v] = \sum_{u \to v} prob[u] / OutDegree[u]

$p r o b [v]$ prob[v] qiyməti yalnız onun bütün sələflərinin ehtimalları yekunlaşdıqdan sonra hesablana bilər. Bu məhz topoloji sıralama ilə verilən emal ardıcıllığıdır: hər təpə, ondan kənar çıxan bütün təpələrdən sonra görünür. Buna görə biz topoloji sıranı Kahn alqoritmi ilə qururuq və eyni zamanda ehtimalları kənarlar boyunca "itələyirik".

Alqoritm belədir:

hər $v$ təpəsi üçün onun giriş dərəcəsini $I n D e g r ee [v]$ InDegree[v] və çıxış dərəcəsini $O u t D e g r ee [v]$ OutDegree[v] hesablayın;
giriş dərəcəsi sıfır olan bütün təpələri növbəyə əlavə edin və $p r o b [r] = 1$ prob[r] = 1 təyin edin;
növbə boş olmayana qədər ondan $v$ təpəsini çıxarın. Bu ana qədər onun bütün sələfləri artıq emal olunub, ona görə $p r o b [v]$ prob[v] qiyməti yekundur. Hər $v \to t o$ v \to to kənarı üçün $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v] qiymətini $p r o b [t o]$ prob[to]-ya əlavə edin və $I n D e g r ee [t o]$ InDegree[to]-nu $1$ azaldın. Əgər $t o$ təpəsinin giriş dərəcəsi sıfır olarsa, onu növbəyə əlavə edin.

Başlanğıcda növbədə təkcə başlanğıc təpə deyil, giriş dərəcəsi sıfır olan bütün təpələr var. $r$ -dən çatıla bilməyən təpələr də emal olunur, lakin onların ehtimalı sıfır olaraq qalır və cavaba təsir etmir.

Cavabın tapılması. Dalan təpələr arasından maksimum $m x$ ehtimalını tapın. Sonra artan sıra ilə $∣ p r o b [v] - m x ∣ \leq 1 0^{- 9}$ |prob[v] - mx| \le 10^{-9} şərtini ödəyən bütün $v$ dalan təpələrinin indekslərini çap edin. Dözümlülüklə müqayisə etmək lazımdır, çünki ehtimallar yuvarlaqlaşdırma xətaları ilə üzən nöqtəli ədədlərdə hesablanır.

Mürəkkəblik. Hər təpə növbəyə dəqiq bir dəfə əlavə olunur və ondan çıxarılır, hər kənar isə bir dəfə baxılır. Alqoritmin işləmə vaxtı $O (n + m)$ O(n + m)-dir.

Misal

Misaldakı qraf üzərində alqoritmi simulyasiya edək. Hər təpənin yanında ona çatma ehtimalı $p r o b [v]$ prob[v] göstərilib. Emal olunmuş təpələr boz rənglə, cari addımda ehtimalın paylandığı kənarlar mavi rənglə, artıq baxılmış kənarlar isə kəsik xətlə göstərilib.

Başlanğıcda (sol şəkil) $p r o b [1] = 1$ prob[1] = 1, digər bütün təpələrin ehtimalı isə $0$ -dır. Təpə $1$ giriş dərəcəsi sıfır olan yeganə təpə olduğundan, növbədən ilk çıxarılan o olur.

$1$ təpəsindən dörd kənar çıxır, ona görə $p r o b [1] = 1$ prob[1] = 1 ehtimalı $2, 3, 4$ və $5$ təpələri arasında bərabər bölünür: hər biri $1/4 = 0.25$ 1 / 4 = 0.25 alır (sağ şəkil). $1$ təpəsindən çıxan kənarları çıxardıqdan sonra $2$ və $3$ təpələrinin giriş dərəcəsi sıfır olur və onlar növbəyə əlavə olunur.

Sonra $2$ təpəsi emal olunur. Ondan iki kənar çıxır, ona görə $p r o b [2] /2 = 0.25/2 = 0.125$ prob[2] / 2 = 0.25 / 2 = 0.125 qiyməti $p r o b [4]$ və $p r o b [5]$ -ə əlavə olunur. Nəticədə $p r o b [4] = p r o b [5] = 0.375$ prob[4] = prob[5] = 0.375 alırıq (aşağı sol şəkil). $5$ təpəsinin giriş dərəcəsi sıfır olur və o növbəyə əlavə olunur.

Sonra $3$ təpəsi emal olunur. Ondan yalnız bir $3 \to 4$ 3 \to 4 kənarı çıxır, ona görə $p r o b [4]$ qiyməti $p r o b [3] /1 = 0.25$ prob[3] / 1 = 0.25 qədər artır və $0.625$ olur (aşağı sağ şəkil). İndi $4$ təpəsi də növbəyə əlavə olunur.

$5$ və $4$ təpələrindən çıxan kənar olmadığından, onların emalı heç bir ehtimalı dəyişmir. Nəticədə alınan topoloji sıra $1, 2, 3, 5, 4$ 1, 2, 3, 5, 4-dür.

Dalan təpələr $4$ və $5$ -dir, ehtimalları isə uyğun olaraq $0.625$ və $0.375$ -dir. Onların cəmi $1$ -ə bərabərdir: biz hardasa mütləq ilişib qalacağıq. Maksimum ehtimal yalnız $4$ təpəsində əldə olunur, bu da cavabdır.

Alqoritmin tətbiqi

$E P S$ sabitini elan edin — üzən nöqtəli ədədləri müqayisə etmək üçün dözümlülük.

#define EPS 1e-9

Giriş qrafını $g$ qonşuluq siyahısı kimi saxlayın. Təpələrin giriş və çıxış dərəcələrini $I n D e g r ee$ InDegree və $O u t D e g r ee$ OutDegree massivlərində saxlayın. $q$ növbəsi Kahn alqoritmində istifadə olunur. $p r o b [v]$ prob[v]-də $v$ təpəsinə çatma ehtimalını hesablayırıq.

vector\u003cvector\u003cint\u003e\u003e g;
vector\u003cint\u003e InDegree, OutDegree;
deque\u003cint\u003e q;
vector\u003cdouble\u003e prob;

Adaların sayı $n$ , körpülərin sayı $m$ və başlanğıc adanın indeksi $r$ -i oxuyun. Qonşuluq siyahısını və dərəcə massivlərini işə salın.

scanf("%d %d %d", \u0026n, \u0026m, \u0026r);
g.assign(n + 1, vector\u003cint\u003e());
InDegree.assign(n + 1, 0);
OutDegree.assign(n + 1, 0);

Körpüləri oxuyun və qrafı qurun. Hər $a \to b$ a \to b kənarı üçün $a$ təpəsinin çıxış dərəcəsini və $b$ təpəsinin giriş dərəcəsini artırın.

for (i = 0; i \u003c m; i++)
{
  scanf("%d %d", \u0026a, \u0026b);
  g[a].push_back(b);
  OutDegree[a]++;
  InDegree[b]++;
}

C++

Giriş dərəcəsi sıfır olan bütün təpələri növbəyə əlavə edin — topoloji sıralama onlardan başlayır.

for (i = 1; i \u003c InDegree.size(); i++)
  if (InDegree[i] == 0) q.push_back(i);

Başlanğıc $r$ təpəsində olma ehtimalı $1$ -dir. Bütün digər təpələr üçün ilkin ehtimal $0$ -dır: $r es i z e$ funksiyası $p r o b$ massivini sıfırlarla doldurur.

prob.resize(n + 1);
prob[r] = 1;

Kahn alqoritmini işə salın. Təpələr növbədən topoloji sırayla çıxarılır.

while (!q.empty())
{

Növbədən $v$ təpəsini çıxarın. Bu ana qədər onun bütün sələfləri artıq emal olunub, ona görə $p r o b [v]$ prob[v] qiyməti yekundur. $(v, t o)$ (v, to) kənarları üzərində iterasiya edin. $v$ təpəsindən $O u t D e g r ee [v]$ OutDegree[v] kənar çıxır, hər biri bərabər ehtimalla seçilir. Buna görə $v \to t o$ v \to to kənarı ilə $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v] ehtimalla hərəkət edirik. Bu qiyməti $p r o b [t o]$ prob[to]-ya əlavə edin.

  v = q.front(); q.pop_front();
  for (int to : g[v])
  {
    prob[to] += prob[v] / OutDegree[v];

$(v, t o)$ (v, to) kənarını qrafdan silin — $t o$ təpəsinin giriş dərəcəsini azaldın.

    InDegree[to]--;

Əgər $t o$ təpəsinin giriş dərəcəsi sıfır olarsa, onun bütün sələfləri emal olunub və $p r o b [t o]$ prob[to] qiyməti yekundur. $t o$ -nu növbəyə əlavə edin.

    if (InDegree[to] == 0) q.push_back(to);
  }
}

Dalan təpələr — çıxış körpüsü olmayan ( $O u t D e g r ee [i] = 0$ OutDegree[i] = 0) adalar — arasında maksimum $m x$ ehtimalını tapın.

mx = 0;
for (i = 1; i \u003c= n; i++)
  if (OutDegree[i] == 0 \u0026\u0026 prob[i] \u003e mx) mx = max(mx, prob[i]);

Ehtimalı $m x$ -dən ən çoxu $E P S$ qədər fərqlənən bütün dalan təpələrin indekslərini artan sıra ilə çap edin. Belə təpələrdən bir neçəsi ola bilər.

for (i = 1; i \u003c= n; i++)
  if (OutDegree[i] == 0 \u0026\u0026 fabs(prob[i] - mx) \u003c= EPS)
    printf("%d ", i);