Задачи по потокам (14 апреля 2016)
- Задачи на паросочетания
- Покрытие вершин орграфа простыми непересекающимися циклами (раздвоили вершины, matching)
- Покрытие вершин ацикличного орграфа минимальным числом путей (раздвоили вершины, matching)
- Теория в форме задач
- k путей (дан орграф, найти k непересекающихся по рёбрам путей из s в t).
- Вершинный поток в орграфе (найти k непересекающихся по вершинам путей)
- Неориентированный граф: два способа создавать ребро.
- Поток в графе с несколькими истоками и стоками
- Избытки и недостатки (есть несколько точек производств, точек потребления, настроить транспортную сеть между ними)
- [L,R]-циркуляция и [L,R]-поток
- Задачи про поток
- Поиск паросочетания в двудольном графе через поток
- Поиск мультипаросочетания (у каждой вершины степень не более k)
- Даны матрицы (девочка, собачка) (девочка, мальчик), найти трисочетание (девочке нравится и мальчик и собачка)
- [не успеем] Турнирная таблица (дана недоигранная таблица игр "каждый с каждым" и итоговые результаты, восстановить счёт).
- [не успеем] Восстановление матрицы (даны суммы в строках, столбцах, некоторые клетки)
- [не успеем] Поиск контролирующего множества min веса, независимого множества max веса
- Кодим
- Поток [code]
- Чуть более быстрый поток [code]
- [не успеем] Декомпозиция потока [code]
- [не успеем] Минимальный разрез
- [не успеем] Удалить в связном неорграфе минимальное число рёбер, чтобы он потерял связность (global cut)
- [не успеем] У каждого ребра в неорграфе есть стоимость. Удалить рёбра минимальной суммарной стоимости, чтобы s и t оказались в разных компонентах связности.
- [не успеем] Проверить, единственный ли минимальный разрез?
- [не успеем] Минимальный и максимальный по количество вершин в половине с истоком