Yalnız Ada#9044

Yalnız Ada (Editoryal)

Soruda belirtildiğine göre, bir adadan ayrıldığınızda ona bir daha asla dönemezsiniz. Dolayısıyla köşeleri adalar, kenarları köprüler olan graf, yönlü döngüsüz bir graf (DAG)'tır. Yalnızca giden köprüsü olmayan bir $v$ adasında, yani çıkış derecesi sıfır olan bir çıkmaz köşede ( $O u t D e g r ee [v] = 0$ OutDegree[v] = 0) sıkışıp kalabilirsiniz.

$p r o b [v]$ prob[v], yürüyüş sırasında $v$ köşesine ulaşma olasılığını göstersin. Başlangıç köşesi için $p r o b [r] = 1$ prob[r] = 1; diğer tüm köşeler için başlangıçta $p r o b [v] = 0$ prob[v] = 0'dır. Graf döngü içermediğinden, her köşe en fazla bir kez ziyaret edilebilir.

$u$ köşesinden $O u t D e g r ee [u]$ OutDegree[u] kadar kenar çıktığını varsayalım. $u$ 'da iken, bunlardan birini eşit olasılıkla rastgele seçeriz, yani $u \to v$ u \to v kenarı boyunca $p r o b [u] / O u t D e g r ee [u]$ prob[u] / OutDegree[u] olasılıkla ilerleriz. $v$ köşesine yalnızca doğrudan öncülerinden ulaşılabilir. Bu nedenle $p r o b [v]$ prob[v], $v$ 'ye giren tüm $u \to v$ u \to v kenarlarının katkılarının toplamına eşittir:

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] değeri yalnızca tüm öncüllerinin olasılıkları kesinleştiğinde hesaplanabilir. Bu tam olarak topolojik sıralama'nın verdiği işleme sırasıdır: her köşe, kendisine kenar giden tüm köşelerden sonra gelir. Bu nedenle, topolojik sırayı Kahn algoritması kullanarak oluşturuyoruz ve aynı anda olasılıkları kenarlar boyunca "iletiyoruz".

Algoritma şu şekildedir:

her $v$ köşesi için giriş derecesini $I n D e g r ee [v]$ InDegree[v] ve çıkış derecesini $O u t D e g r ee [v]$ OutDegree[v] hesapla;
giriş derecesi sıfır olan tüm köşeleri kuyruğa ekle ve $p r o b [r] = 1$ prob[r] = 1 olarak ayarla;
kuyruk boş olmadığı sürece, kuyruktan bir $v$ köşesi çıkar. Bu ana kadar tüm öncülleri işlenmiş olduğundan, $p r o b [v]$ prob[v] değeri kesinleşmiştir. Her $v \to t o$ v \to to kenarı için, $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v] değerini $p r o b [t o]$ prob[to]'ya ekle ve $I n D e g r ee [t o]$ InDegree[to]'yu $1$ azalt. $t o$ köşesinin giriş derecesi sıfır olursa, onu kuyruğa ekle.

Başlangıçta, kuyruk yalnızca başlangıç köşesini değil, giriş derecesi sıfır olan tüm köşeleri içerir. $r$ 'den ulaşılamayan köşeler de işlenir, ancak onların olasılığı sıfır kalır ve sonucu etkilemez.

Cevabı bulma. Çıkmaz köşeler arasında maksimum olasılık $m x$ 'i bulun. Ardından, $∣ p r o b [v] - m x ∣ \leq 1 0^{- 9}$ |prob[v] - mx| \le 10^{-9} koşulunu sağlayan tüm çıkmaz $v$ köşelerinin indekslerini artan sırada yazdırın. Olasılıklar kayan noktalı sayılarla yuvarlama hatalarıyla hesaplandığından, tolerans ile karşılaştırma gereklidir.

Karmaşıklık. Her köşe kuyruğa tam olarak bir kez eklenir ve çıkarılır, her kenar bir kez incelenir. Algoritmanın çalışma süresi $O (n + m)$ O(n + m)'dir.

Örnek

Algoritmayı örnekteki grafik üzerinde simüle edelim. Her köşenin yanında, ona ulaşma olasılığı $p r o b [v]$ prob[v] gösterilmiştir. İşlenmiş köşeler gri ile gölgelendirilmiş, mevcut adımda olasılığın dağıtıldığı kenarlar mavi ile vurgulanmış, önceden incelenmiş kenarlar ise kesikli çizilmiştir.

Başlangıçta (sol şekil) $p r o b [1] = 1$ prob[1] = 1'dir ve diğer tüm köşelerin olasılığı $0$ 'dır. Köşe $1$ , giriş derecesi sıfır olan tek köşedir, bu nedenle kuyruktan çıkarılan ilk köşe odur.

$1$ köşesinden dört kenar çıktığından, $p r o b [1] = 1$ prob[1] = 1 olasılığı $2, 3, 4$ ve $5$ köşeleri arasında eşit olarak bölüştürülür: her biri $1/4 = 0.25$ 1 / 4 = 0.25 alır (sağ şekil). $1$ köşesinden çıkan kenarlar kaldırıldıktan sonra, $2$ ve $3$ köşelerinin giriş dereceleri sıfır olur ve kuyruğa eklenirler.

Sonra, $2$ köşesi işlenir. Ondan iki kenar çıktığından, $p r o b [2] /2 = 0.25/2 = 0.125$ prob[2] / 2 = 0.25 / 2 = 0.125 değeri $p r o b [4]$ ve $p r o b [5]$ 'e eklenir. $p r o b [4] = p r o b [5] = 0.375$ prob[4] = prob[5] = 0.375 elde ederiz (sol alt şekil). Köşe $5$ 'in giriş derecesi sıfır olur ve kuyruğa eklenir.

Sırada köşe $3$ işlenir. Ondan tek bir kenar $3 \to 4$ 3 \to 4 çıktığından, $p r o b [4]$ , $p r o b [3] /1 = 0.25$ prob[3] / 1 = 0.25 kadar artar ve $0.625$ olur (sağ alt şekil). Şimdi köşe $4$ de kuyruğa eklenir.

Köşe $5$ ve $4$ 'ün çıkan kenarı olmadığından, bunların işlenmesi herhangi bir olasılığı değiştirmez. Ortaya çıkan topolojik sıra $1, 2, 3, 5, 4$ 1, 2, 3, 5, 4'tür.

Çıkmaz köşeler $4$ ve $5$ 'tir, olasılıkları sırasıyla $0.625$ ve $0.375$ 'tir. Toplamları $1$ 'e eşittir: bir yerde sıkışıp kalacağımızdan eminiz. Maksimum olasılığa tek bir $4$ köşesinde ulaşılır, bu da cevaptır.

Algoritmanın uygulanması

$E P S$ sabitini tanımlayın — kayan noktalı sayıları karşılaştırmak için tolerans.

#define EPS 1e-9

Giriş grafiğini $g$ komşuluk listesi olarak saklayın. Köşelerin giriş ve çıkış derecelerini $I n D e g r ee$ InDegree ve $O u t D e g r ee$ OutDegree dizilerinde saklayın. Kahn algoritmasında $q$ kuyruğu kullanılır. $p r o b [v]$ prob[v]'de $v$ köşesine ulaşma olasılığını hesaplıyoruz.

vector\<vector\<int\>\> g;
vector\<int\> InDegree, OutDegree;
deque\<int\> q;
vector\<double\> prob;

Ada sayısı $n$ 'i, köprü sayısı $m$ 'i ve başlangıç adasının indeksi $r$ 'yi okuyun. Komşuluk listesini ve derece dizilerini başlatın.

scanf("%d %d %d", &n, &m, &r);
g.assign(n + 1, vector\<int\>());
InDegree.assign(n + 1, 0);
OutDegree.assign(n + 1, 0);

Köprüleri okuyun ve grafiği oluşturun. Her $a \to b$ a \to b kenarı için, $a$ köşesinin çıkış derecesini ve $b$ köşesinin giriş derecesini artırın.

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

C++

Giriş derecesi sıfır olan tüm köşeleri kuyruğa ekleyin — topolojik sıralama bunlarla başlar.

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

Başlangıç köşesi $r$ 'de olma olasılığı $1$ 'dir. Diğer tüm köşeler için başlangıç olasılığı $0$ 'dır: $r es i z e$ fonksiyonu $p r o b$ dizisini sıfırlarla doldurur.

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

Kahn algoritmasını çalıştırın. Köşeler kuyruktan topolojik sırayla çıkarılır.

while (!q.empty())
{

Kuyruktan bir $v$ köşesi çıkarın. Bu ana kadar tüm öncülleri işlenmiş olduğundan, $p r o b [v]$ prob[v] değeri kesinleşmiştir. $(v, t o)$ (v, to) kenarları üzerinde döngü yapın. $v$ köşesinden $O u t D e g r ee [v]$ OutDegree[v] kadar kenar çıkar ve her biri eşit olasılıkla seçilir. Bu nedenle, $v \to t o$ v \to to kenarı boyunca $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v] olasılıkla ilerleriz. Bu değeri $p r o b [t o]$ prob[to]'ya ekleyin.

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

$(v, t o)$ (v, to) kenarını grafikten kaldırın — $t o$ köşesinin giriş derecesini azaltın.

    InDegree[to]--;

$t o$ köşesinin giriş derecesi sıfır olursa, tüm öncülleri işlenmiş demektir ve $p r o b [t o]$ prob[to] değeri kesinleşir. $t o$ 'yu kuyruğa ekleyin.

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

Çıkmaz köşeler — çıkan köprüsü olmayan adalar ( $O u t D e g r ee [i] = 0$ OutDegree[i] = 0) — arasında maksimum olasılık $m x$ 'i bulun.

mx = 0;
for (i = 1; i <= n; i++)
  if (OutDegree[i] == 0 && prob[i] > mx) mx = max(mx, prob[i]);

Olasılığı $m x$ 'ten en fazla $E P S$ kadar farklı olan tüm çıkmaz köşelerin indekslerini artan sırada yazdırın. Böyle birden fazla köşe olabilir.

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