Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 26 27 28 29 30 31 32 >> Отображать по:
#1650
Живопись
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В стране Олимпия очень развита живопись. Картиной считается любой прямоугольник, который состоит из черных и белых единичных квадратов. Художник Олимпус решил радикально улучшить свои картины. Для этого он планирует к белому и черному цветам добавить еще и серый оттенок. По его задумке, граница между каждыми черным и белым квадратом должна содержать серую линию, чтобы образовался эффект плавного перехода.

Однако, перед началом работы, он обнаружил, что серая краска очень дорого стоит. Чтобы сэкономить деньги художник решил оценить, не выгоднее ли сначала перекрасить некоторые белые квадраты в черные, а черные в белые для того, чтобы минимизировать расходы на краску.

Напишите программу, которая по информации о существующей картине определяет минимальную сумму денег, которые понадобятся на ее улучшение.

Формат входных данных

Первая строка входного файла содержит пять натуральных чисел N, M, w, b, g. 1≤N, M≤70 – высота и ширина картины, 1≤w,b,g≤1000 – цена рисования одного белого единичного квадрата, черного единичного квадрата и серой линии единичной длины, соответственно. Далее следует N строк, каждая из которых состоит из M литер. Литера B соответствует черному квадрату, а W – белому.

Формат выходных данных

Единственная строка выходного файла должна содержать одно целое число, которое есть минимальной суммой затрат на улучшение картины.

Примеры
Входные данные
3 2 10 12 1
BW
WB
BW
Выходные данные
7
#1653
Бусинки
  
ограничение по времени на тест
0.3 second;
ограничение по памяти на тест
64 megabytes

Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер – целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых фигур не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой.
Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре (на рисунке эти бусинки выделены темным цветом).

Формат входных данных

В первой строке – количество бусинок 1≤N≤2500. В последующих N-1 строках по два целых числа – номера, соединенных бусинок.

Формат выходных данных

Вывести одно число – искомое количество бусинок.

Пример

Входные данные

Выходные данные

7

4 5

6 7

7 4

7 2

1 3

4 1

5
#1666
Супермногоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих Ki (3 ≤ Ki ≤ 30, 1 ≤ i ≤ N) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:

  1. Oтрезок соединяет только пару супермногоугольников.

  2. Суммарная длина отрезков была минимальна.

  3. Между любыми двумя супермногоугольниками должен существовать путь (последовательность некоторых отрезков и частей границ супермногоугольников).

Формат входных данных

В первой строке число N. В следующих N строках. Число Ki и Ki пар чисел – координаты вершин.

Формат выходных данных

В первой строке число М и сумма длин найденных отрезков с точностью 10-3. В следующих М строках числа L1 X1 Y1 L2 X2 Y2 – номера супермногоугольников и координаты концов отрезков с точностью 10-3.

Примеры

Входные данные

Выходные данные

2

3 1 0 2 0 1 1

4 6 5 7 5 7 6 6 6

1 6.364

1 1.500 0.500 2 6.000 5.000

3

3 0 0 1 0 0 1

4 5 5 6 5 6 6 5 6

3 0 5 1 6 0 6

2 8.000

3 1.000 6.000 2 5.000 6.000

1 0.000 1.000 3 0.000 5.000
#1668
Блохи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Блохи сидят на клетках шахматного поля и ходят конем. Должны собраться в одной из клеток. Определить сумму длин кратчайших путей.

На клеточном поле, размером \(N\)x\(M\) (2 ≤ \(N\), \(M\) ≤ 250) сидит \(Q\) (0 ≤ \(Q\) ≤ 10000) блох в различных клетках. "Прием пищи" блохами возможен только в кормушке - одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.

Входные данные

В первой строке входного файла находится 5 чисел, разделенных пробелом: \(N\), \(M\), \(S\), \(T\), \(Q\). \(N\), \(M\) - размеры доски (отсчет начинается с 1); \(S\), \(T\) - координаты клетки - кормушки (номер строки и столбца соответственно), \(Q\) - количество блох на доске. И далее \(Q\) строк по два числа - координаты каждой блохи.

Выходные данные

Содержит одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.

Примеры
Входные данные
2 2 1 1 1
2 2
Выходные данные
-1
#1683
Распределение заказов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В компанию по обслуживанию компьютеров поступило \(N\) заявок от клиентов. В компании есть \(S\) сотрудников разной квалификации. Руководитель компании знает, какие из заявок каждый сотрудник способен выполнить (возможно, каждый сотрудник может выполнить несколько заявок, также верно, что одну и ту же заявку способны выполнить несколько сотрудников). Каждый сотрудник в какой-то момент времени может выполнять не более одной заявки. Для выполнения каждой заявки достаточно ровно одного сотрудника.

Определите максимальное количество заявок, которые можно начать выполнять при оптимальной загрузке сотрудников.

Входные данные

Cначала вводятся числа \(N\) и \(S\) (натуральные, не превышают 100), затем вводится \(S\) строк по \(N\) чисел в каждой – сведения о квалификации сотрудников. Если в \(j\)-й позиции \(i\)-й строки находится 0, то \(i\)-й сотрудник не способен выполнить данную заявку, если 1 – то способен.

Выходные данные

Выведите единственное число – максимальное количество заявок, которое можно начать выполнять.

Примеры
Входные данные
2 2
1 1 
1 1
Выходные данные
2
Входные данные
3 3
1 0 0
0 1 0
0 0 1
Выходные данные
3
Страница: << 26 27 28 29 30 31 32 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест