Задача на максимум

[mihaild]

fesoh82663, а чем Вас решение tolstopuz не устраивает? (исток и сток в нём просто отдельные вершины, специально для этого созданные)

[fesoh82663]

mihaild в сообщении #1598798 писал(а):

fesoh82663, а чем Вас решение tolstopuz не устраивает? (исток и сток в нём просто отдельные вершины, специально для этого созданные)

Я с макс потоком не очень знаком, поэтому не очень понимаю как мы строим граф. Если я правильно понял, то должно получиться что-то такое.


Поиск максимального потока не предполагает, что у нас один исток и один сток? (тут у нас их несколько)
После того как мы найдем максимальный поток, то искомые переменные будут в ребрах данного графа?

[mihaild]

fesoh82663, в графе есть четыре группы вершин:
1. Исток.
2. Неравенства первой группы.
3. Неравенства второй группы.
4. Сток.
Переменным соответствуют не вершины, а ребра. Точнее, для каждой переменной соединяем ребром включающие её неравенства из первой и второй группы.

[tolstopuz]

Нарисуйте новый исток, из которого будут ребра в вершины $4, 7, 2$, с пропускными способностями соответственно $4, 7, 2$. И новый сток, в который пойдут ребра из вершин $4', 3, 5, 1$, с пропускными способностями $4, 3, 5, 1$. Да, переменные - это шесть нарисованных вами ребер. Их пропускные способности бесконечны, но можно взять, например, максимум из меток вершин, которые это ребро соединяет.

[fesoh82663]

tolstopuz в сообщении #1598812 писал(а):

Нарисуйте новый исток, из которого будут ребра в вершины $4, 7, 2$, с пропускными способностями соответственно $4, 7, 2$. И новый сток, в который пойдут ребра из вершин $4', 3, 5, 1$, с пропускными способностями $4, 3, 5, 1$. Да, переменные - это шесть нарисованных вами ребер. Их пропускные способности бесконечны, но можно взять, например, максимум из меток вершин, которые это ребро соединяет.

Вроде получается такой граф. Т.е. я должен найти поток из вершины s в вершину t и те значения которые получатся на ребрах и будут решением?


p.s. Еще, наверно, ребра у s и t должны быть неориентированы т.к. иначе потока из s в t не существует

[mihaild]

Вроде такой, только ребра которые идут из $t$ должны вести в $t$.

[fesoh82663]

Буду разбираться. Спасибо!