Задача №114746. Дорожные вопросы
Короли Берляндии и Флатландии в очередной раз запланировали дорожные реформы в своих государствах. На этот раз они решили действовать сообща.
Берляндия и Флатландия — два крупных государства, в кажом из которых есть \(n\) городов, между которыми правители хотят построить дороги. В результате тендера короли выбрали \(m\) подрядчиков, \(i\)-й из которых построит двустроннюю дорогу между городами \(a_i\) и \(b_i\) в Берляндии и двустороннюю дорогу между городами \(c_i\) и \(d_i\) во Флатландии, в результате чего суммарное благополучие этих стран возрастёт на \(w_i\). Обратите внимание, что \(w_i\) может быть отрицательным, так как не все подрядчики добросовестно выполняют свою работу. В случае если подрядчик будет нанят, он построит обе дороги, нельзя попросить его построить только одну из них.
Короли Берляндии и Флатландии очень заботятся об экономичности транспортных систем своих стран, а именно они никогда не допустят, чтобы между какими-то двумя городами в их странах существовало два различных простых пути между этими городами. Путь называется простым, если он посещает каждый город не более одного раза, два пути называются различными, если различаются множества дорог, которые эти пути используют. Обратите внимание, что короли могут построить дорожную систему, в которой между некоторыми двумя городами нет пути по дорогам. Иными словами, короли хотят, чтобы графы, образованные дорогами каждой страны, были лесами — множествами неориентированных деревьев.
Короли ещё не решили, сколько же дорог они построят, поэтому просят вас для каждого \(k\) от \(1\) до \(m\) определить, какого максимального суммарного благополучия стран они могут добиться, если наймут \(k\) подрядчиков, при условии, что дорожные сети каждой страны должны получиться экономичными.
В первой строке задано два целых числа \(n\) и \(m\) (\(2 \leq n \leq 800\), \(1 \leq m \leq 800\)) — количество городов в каждой из стран и число подрядчиков, соответсвенно.
В следующих \(m\) строках заданы описания подрядчиков.
Описание \(i\)-го подрядчика задано пятью целыми числами \(a_i\), \(b_i\), \(c_i\), \(d_i\), и \(w_i\) (\(1 \leq a_i, b_i, c_i, d_i \leq n\), \(a_i \neq b_i\), \(c_i \neq d_i\), \(-10^9 \leq w_i \leq 10^9\)) — номера городов в Берляндии, которые соединит дорога \(i\)-го подрядчика, номера городов во Флатландии, которые соединит дорога \(i\)-го подрядчика и величина, на которую возрастёт суммарное благополучие стран, если дороги \(i\)-го подрядчика будут построены.
Выведите \(m\) строк, в \(i\)-й строке выведите одно целое число — максимально возможное суммарное благополучие стран, если будут наняты ровно \(i\) подрядчиков или « Impossible » (без кавычек), если нельзя получить экономичную дорожную сеть, наняв \(i\) подрядчиков.
Рассмотрим первый пример.
При \(k = 1\) выгодно нанять подрядчика с номером \(2\). При \(k = 2\) выгодно нанять подрядчиков с номерами \(2\) и \(3\). Единственный способ нанять трёх подрядчиков — это нанять всех подрядчиков, однако получившаяся дорожная сеть не будет экономичной так как во Флатландии будет существовать два простых пути между городами \(1\) и \(2\) (по дороге, построенной первым подрядчиком, и по дороге, построенной вторым подрядчиком).
В третьем примере все возможные множества подрядчиков построят эффективные дорожные сети.
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(w_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 15 | \(n \leq 40\) | \(m \leq 20\) | – | 0 | |
| 2 | 6 | – | \(m = n - 1\) | – | – | \(a_i = i, b_i = i + 1\) |
| 3 | 15 | – | – | \(w_i = 0\) | – | |
| 4 | 17 | \(n \leq 70\) | \(m \leq 70\) | – | 0, 1 | |
| 5 | 8 | \(n \leq 150\) | \(m \leq 150\) | – | 0, 1, 4 | |
| 6 | 14 | \(n \leq 500\) | \(m \leq 500\) | – | 0, 1, 4, 5 | |
| 7 | 25 | – | – | – | 0, 1, 2, 3, 4, 5, 6 | |
4 3 1 2 1 2 7 1 3 2 1 8 2 3 3 2 6
8 14 Impossible
6 4 1 2 1 3 34 2 3 3 2 11 2 4 3 1 5 2 1 3 5 8
34 45 24 Impossible
3 2 3 1 2 3 -9 2 3 1 3 -21
-9 -30