Прошу помочь с идеей решения этой задачи. Я строю сеть. Вершинами являются маги, моменты времени, сток и исток. Нахожу максимальный поток в сети, что дает мне ответ "Yes" или "No". Но не могу восстановить ответ, т.к. матрица потока не дает ответ.
Прошу помочь с идеей решения этой задачи. Я строю сеть. Вершинами являются маги, моменты времени, сток и исток. Нахожу максимальный поток в сети, что дает мне ответ "Yes" или "No". Но не могу восстановить ответ, т.к. матрица потока не дает ответ.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 4 | AmShZ | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
Сейчас проходил у меня только поток.
в таком случае нужно поздравить тимус с фэйлом и ждать справедливого режаджа, который, почему-то, не случился вовремя
например вот http://acm.timus.ru/rating.aspx?space=1&num=1200&pos=1401
ограничение времени по задаче 0.25 сек.
а на последнем месте в рейтинге авторов решение с временем 0.821 сек.))
5 2
0 2
0 3
0 5
3 2
3 2
Исправил)))
P. S.
Граф состоит из двух долей. Левая доля - маги (N штук), правая доля - время. От истока ко всем магам идут ребра пропускной способностью 2 (каждого мага надо побрить 2 раза). От каждого мага (вершины левой доли) к вершинам, обозначающим время, идут ребра пропускной способностью 1. Причем только к тем вершинам из правой доли, в которые маг может быть побрит (по входным данным). От каждой вершины правой доли в сток идут ребра пропускной способностью k (в каждый момент времени можно побрить не более k магов).
Теперь в таком графе надо найти поток. Если он будет равен 2*N (каждого мага побрили по 2 раза), то ответ "Yes" , иначе "No". Если ответ положительный, то моменты времени восстановить не сложно. Используемые ребра в матрице смежности будут равны нулю.
Цикл по магам (i)
Цикл по возможному времени для мага (j)
Если в матрице смежности на позиции [i][j] находится 0. То именно в этот момент мы побрили этого мага.
S 1 2 3 7 8 9 T
S 0 2 2 2 0 0 0 0
1 0 0 0 0 1 1 1 0
2 0 0 0 0 1 1 1 0
3 0 0 0 0 1 1 1 0
7 0 0 0 0 0 0 0 2
8 0 0 0 0 0 0 0 2
9 0 0 0 0 0 0 0 2
T 0 0 0 0 0 0 0 0
Найден путь S - 1 - 7 - T ([S][1]; [1][7]; [7][T] получают "- 1"; [T][7]; [7][1]; [1][S] "+1")
S 1 2 3 7 8 9 T
S 0 1 2 2 0 0 0 0
1 1 0 0 0 0 1 1 0
2 0 0 0 0 1 1 1 0
3 0 0 0 0 1 1 1 0
7 0 1 0 0 0 0 0 1
8 0 0 0 0 0 0 0 2
9 0 0 0 0 0 0 0 2
T 0 0 0 0 1 0 0 0
И т.д.
В результате часть результирующей матрицы будет равна
7 8 9
1 0 0 1
2 0 1 0
3 1 0 0
Означает, что первый маг побрит в моменты 7,8. Второй в - 7,9. Третий в - 8,9. (там где 0 в матрице)