Problem S. 70. (March 2012)
S. 70. Adam moved to Nameless City and immediately drew a precise map to grasp every detail: he recorded the length of each street on his map in micrometers. Of course, he is also a very careful route planner: he now wants to get from A to B by minimizing the difference between the lengths of the longest and shortest streets on his route. Your program should determine such a route for Adam.
Your program reads the description of the city from the standard input. The first line of the input contains the number of road crossings N and (after a space separator) the number of streets M connecting them (1
N1000, 0M5000). The second line of the input identifies crossings A and B by giving their numbers. Then each of the following M lines describes a street in a form XiYiLi, where Xi and Yi are the numbers of the crossings connected by street i,finally Li denotes the length of street i (1Li109). Assume that the two endpoints of a street are always disjoint, further, there are no two streets having both endpoints in common. Crossings are numbered from 0 to N-1.
The single line on the standard output should contain a single number: the minimal attainable difference, if A is connected with B, and -1 otherwise.
In the example, Példa bemenetek are sample inputs, while Példa kimenetek are the corresponding outputs.
In order to obtain the maximal number of points, your code should handle our largest test cases within 1 second.
The source code of your program (s70.pas, s70.cpp, ...) -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted in a compressed file s70.zip, also containing a brief description of your solution (s70.txt, s70.pdf, ...) and the name of the developer environment to use for compiling.
(10 pont)
Deadline expired on April 10, 2012.
Sorry, the solution is available only in Hungarian. Google translation
A bemenetben megadott kereszteződéseket és utcákat tekinthetjük egy gráf csúcsainak és éleinek, ahol az élek meg vannak címkézve az utca hosszával. Ekkor az a feladat, hogy keressünk a két megadott csúcs között egy olyan utat, amelyen a legrövidebb és a leghosszabb él különbsége minimális.
Backtrack
Egy egyszerű (de lassú) megoldás, hogy visszalépéses kereséssel meghatározzuk az összes lehetséges útvonalat A-ból B-be, közben mindegyikre kiszámoljuk a legrövidebb és a leghosszabb él különbségét, és ezeken végzünk egy minimumkeresést. Ez a megoldás körülbelül 20-as csúcsszámig fut le időben. Hibátlan megvalósítása (megfelelő dokumentációval együtt) 5 pontot ért.
Ötlet
A jobb megoldások alapötlete, hogy rendezzük az éleket hosszuk szerint. Ekkor a feladat a következő: egy olyan intervallumot keresünk a rendezett sorozaton, amelyre igaz, hogy az A csúcsból elérhető a B csúcs csak az intervallum beli éleket használva, és az intervallum kezdő és végpontjában lévő élek hosszának különbsége minimális.
Köbös megoldás
Ebből máris adódik egy olyan megoldás, aminek a futásideje az élek számának köbével arányos. Nézzük végig az összes lehetséges intervallumot (ez idáig O(M2)), és mindegyikre döntsük el, hogy van-e csak a benne lévő éleket használó A->B út (ez egy O(M)-es szorzó a futásidőn). Ez az algoritmus azonban nem fér bele az 1 másodperces futási időlimitbe.
Minimális feszítőfát használó megoldások
Vegyük észre, hogy ha adott az intervallum alsó széle, akkor az (itt kezdődő intervallumok közül) optimális felső szél megtalálása majdnem a minimális feszítőfa problémája azon a gráfon, ami abban különbözik az eredetitől, hogy elhagytuk az alsó szélnél kisebb súlyú éleket. A különbség csak annyi, hogy itt fa helyett elég egy olyan élhalmaz, amit használva létezik A->B út, és a minimalitási feltétel összeg helyett a maximális súlyú élre vonatkozik. A Kruskal és a Prim algoritmus is könnyen módosítható erre a célra, ugyanis mindkettőnél csak annyit kell tenni, hogy megállunk akkor, amikor a feldolgozott éleken már elérhető A-ból B (a minimális összsúlyú feszítőfa mindenképpen rendelkezik a minimális maximális súlyú él tulajdonsággal is (egyébként fordítva ez nem igaz)).
Vagyis ha meghatározzuk az összes élre, hogy mennyi a hozzá tartozó optimális felső határ, és ezeken végzünk egy minimumkeresést, akkor megkapjuk a megoldást. A futásidő O(M2log M) a Prim algoritmus esetén. A Kruskal algoritmust a union-find nevű adatszerkezettel megvalósítva a futasidő O(M2
(M)) (a rendezés miatti log M-es szorzó azért nem jelenik meg, mert elég egyszer rendezni az elején), amit tekinthetünk gyakorlati szempontból O(M2)-nek.
Az implementáció: S70KruskalUnionFind.cpp
Mivel minimális összsúlyú feszítőfa helyett most a legnagyobb súlyú él minimalizálása a cél, ezért alkalmazhatunk bináris keresést is az optimális felső szél keresésekor (a fölfelé vagy lefelé lépés döntését egy bejárással végezzük). Ennek bemutatására Szabó Attila megoldását közöljük: S70SzaboAttila.zip
Intervallum-léptetés
Strenner Péter megoldása nem használja a minimális feszítőfa fogalmát, hanem egy másik, nagyon tanulságos módszert alkalmaz: Legyen kezdetben az [x, y] intervallum csak az első élt tartalmazó intervallum. Minden lépésben megnézzük, hogy elérhető-e A-ból B csak az [x, y] beli éleken (ahol x és y élek sorszáma a hossz szerinti rendezésben), és ha igen, akkor az x-et növeljük, különben az y-t. Az így előforduló intervallumok közül a legrövidebbnek a hossza a megoldás. A futasidő O(M2), mivel az intervallum eleje és vége is legföljebb M-szer lép, és lépésenként egy O(M)-es bejárást végzünk.
Ugyanez C++-ban implementálva: S70IntervallumLeptetes.cpp
Egyébként ezzel a módszerrel lehet megoldani pl. a 2008-2009-es OKTV 3. korcsoport 3. forduló 1. feladatát is.
O(M log M)
Ugyan az O(M2)-es megoldások beleférnek az 1 másodperces futási időlimitbe, de létezik egy még gyorsabb megoldás is: ugyanazt csináljuk, mint az intervallum-léptetős, csak az A->B elérhetőséget ezzel az adatstruktúrával tartjuk számon: Link/cut tree
Statistics:
12 students sent a solution. 10 points: Strenner Péter, Szabó 928 Attila. 8 points: 3 students. 7 points: 1 student. 6 points: 1 student. 5 points: 3 students. 4 points: 1 student. 2 points: 1 student.
Problems in Information Technology of KöMaL, March 2012