Zadania na kółko 07.02

Odśnieżanie

W nieskierowanym, ważonym, spójnym grafie wyróżniono cztery wierzchołki. Należy usunąć część krawędzi z grafu tak, żeby nadal istniały ścieżki pomiędzy każdą parą wyróżnionych wierzchołków i żeby suma wag krawędzi, które pozostały w grafie, była jak najmniejsza.
Liczba wierzchołków, krawędzi <= 2 * 10^5

Szkolne porachunki

Jasio ostatnio zadarł z dresami. Niestety, planują oni zamach na niego. Jasio wie, że należy się od nich trzymać z daleka. Niestety, trzeba chodzić do szkoły. Na szczęście dresy do szkoły nie chodzą, więc siedzą w domu nieruszając się (póki Jasio nie przejdzie odpowiednio blisko). Dana jest prostokątna mapa z zaznaczoną pozycją Jasia, pozycjami dresów, pozycją szkoły oraz pozycjami przeszkód. Odległość między pozycjami mierzymy w metryce Manhattan. Wyznacz największą możliwą odległość od najbliższego dresa na mapie na drodze Jasia do szkoły.
Wysokość i szerokość mapy <= 1000

Spokój

Hotel, w którym odbywa się obóz informatyczny, można przedstawić jako graf (krawędzie to korytarze, wierzchołki to pokoje lub skrzyżowania korytarzy). Każdemu gimbusowi na obozie należy przydzielić dwa różne pokoje - jeden do pracy, drugi do spania. Dodatkowo każdy gimbus musi mieć przydzieloną swoją jednoznaczną trasę (ścieżkę) między pokojami, po której będzie się poruszać. Należy tak przydzielić gimbusom pokoje i trasy, aby trasy dowolnych dwóch gimbusów były rozłączne krawędziowo. Powiedz, ile maksymalnie gimbusów można wziąć na obóz.
Liczba wierzchołków, krawędzi w grafie <= 50000.

Ustawka

W grze Ustawka bierze udział 2n graczy podzielonych na dwie drużyny po n osób. Każda z uczestników wybiera sobie jeden cel z przeciwnej drużyny. Zastanawiamy się, czy w trakcie zabawy znajdzie się elitarny zbiór E, taki że:

  • Żaden uczestnik z E nie zostanie zaatakowany przez innego uczestnika z E.
  • Każdy uczestnik, który nie należy do E zostanie zaatakowany przez kogoś z E.

Mając dany zbiór atakujących się uczestników, znajdź zbiór E wiedząc, że taki istnieje.
n <= 100 000