АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Замечание. Сеть является ориентированным графом

Читайте также:
  1. Важное замечание
  2. Замечание
  3. Замечание
  4. Замечание
  5. Замечание автора
  6. Замечание о принципе тождественности
  7. Замечание.

Сеть является ориентированным графом.

 

Выход

В выходной файл запишите величину максимального потока и минимальную суммарную стоимость максимального.

Примеры входа и выхода

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, vN), где 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, vN), где 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  

 


1 | 2 | 3 | 4 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)