>>2274317
1)Расстояние между вершинами:
Классический алгоритм Дейкстры.
2)Разрушение дорог:
Классический алгоритм Штор-Вагнера.
3)Студентам - бесплатно:
Будем ассоциировать строки и столбцы матрицы с вершинами графа. Ребро из вершины строки i в вершину столбец j есть только тогда, когда во входных данных есть клетка (i,j). Теперь задача следующая: покрасить рёбра в красный и синий так, чтобы для каждой вершины кол-во исходящих красных рёбер было примерно равно кол-ву исходящих синих рёбер. Рассмотрим этот граф: он двудолен, теперь создадим ещё две фиктивные вершины (по одной в каждую долю) fict1 и fict2. Из fict1 проведём ребра во все вершины второй доли, имеющих нечётную степень из fict2 проведём рёбра в вершины первой доли имеющих нечётную степень. Можно заметить, что степени вершины fict1 и вершины fict2 имеют одинаковую чётность. Поэтому если степень вершин нечётна, то проведём ещё одно ребро (fict1-fict2). Теперь в графе все вершины имеют чётную степень, а это значит ровно то, что в каждой компоненте этого графа существует Эйлеров цикл. Запустим серию эйлеровых обходов в каждой компоненте, каждое второе ребро в эйлеровом цикле покрасим в красный, каждое первое - в синий. Как-то так.
4)Джак изкормвача:
Рассмотрим следующий граф который имеет следующие группы вершин:
Исток
Вершины-буквы-алфовита ('a'-'z')
Вершины-буквы-в-странице (p,i,j)
Фиктивные "развязки" (индивидуальны для каждой пары параллельных букв на странице)
Сток
Рассмотрим какую-нибудь букву на странице c1 с координатами(p,i,j) и параллельную ей с2 (p,i,W-j+1).
Запустим ребро с пропуск. способностью 1 из (p,i,j) в фиктивную "развязку"
Запустим ребро с пропуск. способностью 1 из (p,i,W-j+1) в фиктивную "развязку"
Запустим ребро c пропуск. способностью 1 из фиктивной "развязки" в сток.
Запустим ребро с пропуск. способностью 1 из вершины буквы-алфовита c1 в вершину (p,i,j)
Запустим ребро с пропуск. способностью 1 из вершины буквы-алфовита c2 в вершину (p,i,W-j+1)
Запустим ребро с пропуск. способностью "кол-во букв C в строке S" из истока в вершину-букву алфовита C.
Если максимальный поток в таком графе будет равен длине строки - ответ "YES" иначе "NO". Максимальный поток нужно искать быстро (алгоритмом Диница например, Форд-Фалкерсон с масштабированием не проходил).
5) Ладдейная атака.
Будем ассоциировать вершины со строками и столбцами. Запустим из каждой вершины строки ребро в вершину столбец, если клетка вырезана, то не будем запускать ребро. Величина наибольшого паросочетания в таком графе и будет ответом. Наибольшее паросочетание ищется алгоритмом Куна.