NézetNyomtat

Szolga (Megoldás)
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok
Címkék > Hiányzó algoritmus

Szolga

Egy számítógépes hálózat $N$ csomópontot tartalmaz. Azt mondjuk, hogy az $Y$ csomópont közvetlen szomszédja az $X$ csomópontnak, ha össze vannak kötve kétirányú adatátvitelt biz­tosító közvetlen vonallal. (Tehát, ha $Y$ szomszédja $X$-nek, akkor $X$ is szomszédja $Y$-nak.) Van $K$ darab csomópont, amelyek névfeloldó szolgáltatást tudnak adni. Ha egy csomópontban lévő gép névfeloldást kíván, akkor a kérését el kell juttatnia vala­melyik kiszolgálóhoz. Ha valamelyik közvetlen szomszédja kiszolgáló, akkor a kérését ennek továbbítja, amelyik azt meg is válaszolja. Egyébként a kérést valamelyik közvetlen szomszéd­jának kell átadni, aki azt továbbítja, és így tovább, amíg a kérés valamelyik kiszolgálóhoz nem ér, aki megválaszolja, és visszaküldi a választ ugyanazon útvonalon, amelyiken érkezett. A válaszidőt az határozza meg, hogy hány csomóponton keresztül jut el a kérés a kiszolgá­lóhoz.

Feladat

Készíts programot (SZOLGA.PAS, ...), amely minden csomópontra kiszá­mítja, hogy a csomópont melyik közvetlen szomszédjának küldje a kérést, ha az a cél, hogy a legrövidebb időn belül megkapja a választ!

Bemenet

A SZOLGA.BE szöveges állomány első sorában a csomópontok $N$ $(1\leq N\leq 10000)$ száma, és a kiszolgálók $K$ $(1\leq K\leq 1000)$ száma van. A csomópontokat az $1,\ldots,N$ számokkal azonosít­juk. A második sor a $K$ kiszolgáló sorszámait tartalmazza egy-egy szóközzel elválasztva. A következő $N$ sor írja le a hálózatot. Az állomány $i+2$-edik sorában azok a csomópontok van­nak felsorolva egy-egy szóközzel elválasztva és 0-val zárva, amelyek az $i$ csomópont közvet­len szomszédjai. A hálózat legfeljebb 100000 közvetlen vonalat tartalmaz.

Kimenet

A SZOLGA.KI szöveges állomány első sorába azt az $M$ számot kell írni, amelyre teljesül, hogy bármely csomópont kérése megválaszolható úgy, hogy legfeljebb $M$ csomóponton ke­resztül jut el a kérés valamely kiszolgálóhoz (beleértve a kiszolgálót, de nem számítva a ké­rést küldőt)! A következő $N$ sor mindegyikébe két számot kell írni, az $i+1$-edik sorban az első szám a legkevesebb csomópont száma, amelyen keresztülhalad az $i$-edik csomópont kérése! A második szám pedig annak a csomópontnak a sorszáma legyen, amelyiknek az $i$ csomópont a kérését továbbítja! A kiszolgálók esetén a 0 i számpár legyen kiírva! Ha nincs olyan útvonal, amelyen az $i$-edik csomópont eljuthatna valamely kiszolgálóhoz, akkor a 0 0 számpárt kell ki­írni. Több megoldás esetén bármelyik megadható.

Példa

SZOLGA.BESZOLGA.KI
11 3
1 3 5
4 0
11 0
4 6 5 0
1 3 6 8 0
7 3 6 0
4 3 5 7 10 8 0
5 6 10 0
4 6 9 0
8 10 0
9 6 7 0
2 0

3
0 1
0 0
0 3
1 1
0 5
1 3
1 5
2 4
3 8
2 6
0 0

Tesztadatok

Nincs.