|
Дороги - 3
(Время: 1 сек. Память: 16 Мб Сложность: 67%)
Начинается зима, но в городе К на дорогах все еще продолжается ремонт. После того, как очередная дорога была отремонтирована, департамент транспорта пришел к выводу, что дешевле обслуживать дороги с односторонним движением.
Сейчас все дороги в городе К двусторонние. Дорога состоит из двух полос – встречного и попутного направления. Требуется превратить максимальное количество дорог в односторонние, оставив одну из двух полос так, чтобы сообщение между точками города не нарушилось. Это означает, что если из точки i можно проехать в точку j (прямо или через промежуточные точки), то после введения одностороннего движения эта возможность должна остаться.
Карта города задаётся матрицей смежности M, заполненной нулями и единицами. Размерность матрицы N (1 ≤ N ≤ 100) – число точек города. Если M[i, j] = 1, то существует полоса для перемещения из точки i в точку j, не проходящая через другие точки, иначе M[i, j] = 0 (M[i, i] = 0 для любого i). Матрица M симметрична относительно главной диагонали, т.е. M[i, j] = M[j, i], что означает двустороннюю дорогу (полоса встречного и попутного направления).
Входные данные
В первой строке входного файла INPUT.TXT содержится натуральное число N – размерность матрицы M, следующие N строк, каждая по N символов (нули или единицы), разделенные пробелами – элементы матрицы M.
Выходные данные
В выходной файл OUTPUT.TXT выведите максимально возможное число двусторонних дорог, которые можно превратить в односторонние.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
0 0 1 1
0 0 0 0
1 0 0 1
1 0 1 0 | 3 |
| 2 | 7
0 1 0 1 0 0 0
1 0 0 1 0 1 0
0 0 0 0 1 1 1
1 1 0 0 0 0 0
0 0 1 0 0 1 0
0 1 1 0 1 0 0
0 0 1 0 0 0 0 | 6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
