Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Дороги - 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.TXTOUTPUT.TXT
14
0 0 1 1
0 0 0 0
1 0 0 1
1 0 1 0
3
27
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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru