ACM 1995

regionális verseny


Non-stop utazás
Dávid nem szeret az elsőbbségadás tábláknál, stoptábláknál, jelzőlámpáknál várakozni. Annak érdekében, hogy minimalizálja ezt a várakozási időt, térképet készített minden olyan régióról, amelyben gyakran utazik. Ezeken a térképeken megjelölte az általa mért átlagos várakozási időt minden útkereszteződésben. Minden régióban adott két kitüntetett pont, amelyek közt Dávid szeretné megtalálni a legrövidebb várakozási időt igénylő utat, tekintet nélkül az út távolságban mért hosszára.

Bemenet:

Az INPUT.TXT állomány tartalmazza a Dávid által készített térképek leírását. Minden régió térképének leírása a benne szereplő útkereszteződések számával (Ni) kezdődik. Egyetlen régió sem tartalmaz tíznél több útkereszteződést. A régiókon belül a kereszteződések 1-től kezdve szekvenciálisan vannak sorszámozva. Az útkereszteződések számát követő Nj sor mindegyikében egy-egy útkereszteződés specifikációja található. Minden ilyen sor a kereszteződést elhagyó utcák számával kezdődik, majd minden ilyen utcára, az utca másik végén található kereszteződés sorszámával, és az aktuális kereszteződésben a Dávid által mért átlagos várakozási idővel folytatódik. Minden régió utolsó útkereszteződésének adatai után két kereszteződés sorszáma található. Ezek közül az első annak a sorszáma, ahonnan Dávid megkezdi az útját, a második pedig annak a sorszáma, ahol befejezi. A teljes inputot — mely a régiók leírásának sorozatából áll — egyetlen 0 zárja.
Kimenet:
Írjuk az eredményeket az OUTPUT.TXT nevű állományba! Minden régióhoz egyetlen sor tartozik. Ez tartalmazza a legrövidebb várakozási időt igénylő úton szereplő kereszteződések sorszámait, valamint a minimális várakozási időt. A példa egy alkalmas formátumot mutat, de más output formátum is elfogadható.
Megjegyzések:
1. Minden régióban egyetlen minimális várakozási időt igénylő út van
2. Az átkereszteződések közti utcák egyirányúak. Az i és j útkereszteződések közti kétirányú utca reprezentálásához az input tartalmaz (i,j) és (j,i) utcát is.
3. Bármely i és j útkereszteződések közt legfeljebb egy utca lehetséges.
Példa:
 
INPUT.TXT OUTPUT.TXT
5
2 3 3 4 6
3 1 2 3 7 5 6
1 4 5
0
1 4 7
2 4
2
1 2 5
1 1 6
1 2
0		 Teszt#1: Útvonal: 2 1 4 Várakozási idő: 8
Teszt#2: Útvonal: 1 2 Várakozási idő: 5

Gráfok színezése
Írjunk programot, amely megkeresi egy adott gráf optimális színezését! Gráf színezése alatt a csúcsok fekete vagy fehér színnel való színezését értjük. A színezést optimálisnak nevezzük, ha a fekete csúcsok száma maximális. A színezéseket megszorítjuk azzal a feltétellel, hogy fekete csúcsok nem lehetnek szomszédosak. Az ábrán a példában szereplő gráf egy optimális színezése látható három fekete csúccsal.

Bemenet:

A gráf csúcsait az  (n<=100) számokkal, éleit (n1, n2) párokkal (n1<>n2) adjuk meg. Az input fájl m gráf leírását tartalmazza. Az input első sora tartalmazza az m számot. Minden gráf leírásának első sora az n és k egészekből áll; n a gráf csúcsainak, k az éleinek a száma. Az ezt követő k sor mindegyike a gráf egy élét írja le, az él végpontjainak azonosítói által.
Kimenet:
Az output minden gráfhoz két sort, összesen 2m sort tartalmaz. Az első sor a gráfban feketére színezhető csúcsok maximális számát tartalmazza. A második sor egy optimális színezésben a fekete csúcsok azonosítóiból áll.
Példa:
 
INPUT.TXT OUTPUT.TXT
1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6		 3 
1 4 5