 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Замечание. Сеть является ориентированным графом
|
Читайте также: |
Сеть является ориентированным графом.
Выход
В выходной файл запишите величину максимального потока и минимальную суммарную стоимость максимального.
Примеры входа и выхода
| input.txt | output.txt |
| 6 1 6 1 2 1 4 2 3 1 12 3 6 1 7 5 6 1 9 2 5 1 6 4 3 1 1 1 4 1 1 |
Лабораторная работа «Задача о различных путях»
Входной файл: input.txt
Выходной файл: output.txt
Ограничение времени: 1 секунда на тест
Дан орграф. Найти максимальное количество различных путей между двумя заданными вершинами орграфа (пути считаются разными, если они не имеют ни одной общей вершины за исключением начальной и конечной).
Вход
В первой строке входного файла записано количество вершин графа N (2 ≤ N ≤ 100). В остальных строках записан список дуг графа. Каждая дуга задана парой целых чисел u, v (1 ≤ u, v ≤ N), где u, v - номера вершин.
Выход
В выходной файл запишите максимальное количество различных путей между вершинами 1 и N.
Примеры входа и выхода
| input.txt | output.txt |
| 1 2 1 4 2 4 2 6 4 6 6 5 2 5 6 7 5 7 |
Лабораторная работа «Минимальное покрытие путями»
Входной файл: input.txt
Выходной файл: output.txt
Ограничение времени: 2 секунды на тест
Дан ациклический орграф. Найти минимальное покрытие графа путями.
Вход
В первой строке входного файла записано количество вершин графа N (2 ≤ N ≤ 500). В остальных строках записан список дуг графа. Каждая дуга задана парой целых чисел u, v (1 ≤ u, v ≤ N), где u, v - номера вершин.
Выход
В выходной файл записать количество путей в минимальном покрытии графа.
Примеры входа и выхода
| input.txt | output.txt |
| 1 7 2 7 2 6 3 7 3 6 4 7 4 6 4 5 4 3 4 2 5 3 5 6 5 7 7 6 |
Лабораторная работа «Задача о назначениях»
Входной файл: input.txt
Выходной файл: output.txt
Ограничение времени: 1 секунда на тест
Даны N деталей и N станков. Известны стоимости изготовления каждой детали на каждом станке. Найти такое распределение деталей по станкам, для которого суммарная стоимость работ минимальна. На одном станке можно изготовить только одну деталь.
Вход
В первой строке входного файла записано целое число N (1 ≤ N ≤ 200) и матрица стоимостей { Aij } i, j = 1... N. Элементы матрицы - целые неотрицательные числа, не превышающие 104. Число Aij равно стоимости изготовления детали номер i на станке номер j.
Выход
В выходной файл запишите минимальную суммарную стоимость изготовления всех деталей и оптимальное распределение деталей в виде последовательности номеров станков, назначенных для каждой из деталей (в порядке возрастания номеров деталей).
Примеры входа и выхода
| input.txt | output.txt |
| 7 3 5 8 5 6 2 3 5 | 2 3 1 |
Поиск по сайту: