ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1709. Пингвин-Авиа

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Авиакомпания Пингвин-Авиа, как и многие другие антарктические авиакомпании, испытывает финансовые трудности в период мирового экономического кризиса. Жители Антарктиды теперь экономят на полётах и чаще пользуются поездами или вообще предпочитают сидеть дома. Руководство авиакомпании надеется, что летом поток клиентов возрастёт за счёт желающих отдохнуть на приморских курортах Антарктиды. Чтобы дотянуть до лета, было решено оптимизировать схему авиарейсов, временно сократив часть рейсов и, возможно, введя несколько новых.
Директор Пингвин-Авиа считает, что после оптимизации схема полётов должна обладать следующими свойствами:
  1. Рейсами Пингвин-Авиа можно добраться из любого аэропорта Антарктиды до любого другого. Возможно, для этого придётся сделать несколько пересадок.
  2. Схема должна содержать минимальное число рейсов среди всех схем, отвечающих первому свойству.
Но в Антарктиде не всё так просто. За отмену существующего рейса с авиакомпании взимается разовая неустойка в размере d антарктических долларов. Кроме того, чтобы получить слоты под новый рейс, надо дать взятку крёстному отцу антарктической мафии по прозвищу Белый медведь в размере a антарктических долларов.
Помогите директору Пингвин-Авиа трансформировать существующее расписание полётов, потратив при этом наименьшую сумму денег, и вы получите за это проездной билет на все рейсы авиакомпании.

Исходные данные

В первой строке записано целое число n — количество аэропортов в Антарктиде, 2 ≤ n ≤ 100. Во второй строке через пробел записаны целые числа d и a, 1 ≤ d, a ≤ 106. В следующих n строках записана существующая схема полётов Пингвин-Авиа в виде матрицы размером n × n. В ячейке (i, j) матрицы стоит единица, если авиакомпания совершает рейс между аэропортами i и j. В противном случае в ячейке стоит нуль. Гарантируется, что матрица симметрична и на её диагонали стоят нули.

Результат

В первой строке выведите наименьшую сумму денег, которую придётся потратить для оптимизации существующей схемы полётов. В следующих n строках выведите план изменения схемы в виде матрицы размера n × n. Ячейка (i, j) матрицы содержит символ «d», если нужно отменить существующий рейс между аэропортами i и j. Если нужно ввести новый рейс между этими аэропортами, ячейка содержит символ «a». Все остальные ячейки матрицы содержат символ «0». Матрица должна быть симметричной. Если существует несколько оптимальных схем, выведите любую из них.

Пример

исходные данныерезультат
6
2 3
011000
101000
110000
000011
000101
000110
7
0d0000
d00000
000a00
00a0d0
000d00
000000
Автор задачи: Александр Ипатов
Источник задачи: XIII чемпионат Урала по спортивному программированию, 4 апреля 2009 г.