Mosty (omówienie)

15.01.2011

Dla dwóch mostów A oraz B z treści zadania są trzy możliwości ich wzajemnego położenia:

  • mosty A i B są rozłączne - ich zasięgi nie mają części wspólnej, np. A odpowiada za odcinek (1,6) a B za odcinek (8,13). Wtedy ich wzajemne położenie ze względu na poziom jest zupełnie nieistotne ( nieważne, czy A będzie miało wyższy poziom niż B czy na odwrót - i tak liczba punktów przecięć między tymi mostami będzie wynosiła 0 )
  • mosty A i B przecinają się w jednym punkcie - ich zasięgi mają część wspólną, ale żaden nie zawiera się w drugim, np. A odpowiada za odcinek (1,7) a B za odcinek (5,14). Wtedy ich wzajemne położenie ze względu na poziom znów jest nieistotne, bo zawsze będą generowały jeden punkt przecięcia, którego nijak nie da się uniknąć
  • zasięg jednego mostu zawiera się w zasięgu drugiego, np. A odpowiada za odcinek (1,10) a B za odcinek (3,8). Gdyby B znajdował się na wyższym poziomie niż A, to utworzyłyby się aż 2 nowe punkty przecięcia. Jeśli natomiast most A będzie miał wyższy poziom, to tych punktów będzie 0.

Widać więc, że jedyne na czym nam zależy, to to, aby mosty "zawierające się" były na niższych poziomach niż mosty "zawierające". Utwórzmy graf skierowany, w którym wierzchołkami będą mosty, a krawędź z A do B oznacza, że B zawiera się w A ( czyli B ma być na niższym poziomie ). Łatwo zauważyć, że taki graf jest acykliczny, można więc posortować go topologicznie. Wynikiem będzie właśnie posortowanie topologiczne najmniejsze leksykograficznie. Wymaganie leksykograficzne można spełnić zachłannie, wg następującego algorytmu:

dopóki istnieją jeszcze wierzchołki w grafie
    wybierz wierzchołek o najmniejszym możliwym numerze, z którego nie wychodzą krawędzie
    usuń ten wierzchołek z grafu

Algorytm ten można łatwo zaimplementować w czasie O(n2), co wystarczyło na uzyskanie maksymalnej liczby punktów.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com