Прошу помочь с идеей решения этой задачи. Я строю сеть. Вершинами являются маги, моменты времени, сток и исток. Нахожу максимальный поток в сети, что дает мне ответ "Yes" или "No". Но не могу восстановить ответ, т.к. матрица потока не дает ответ.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Прошу помочь с идеей решения этой задачи. Я строю сеть. Вершинами являются маги, моменты времени, сток и исток. Нахожу максимальный поток в сети, что дает мне ответ "Yes" или "No". Но не могу восстановить ответ, т.к. матрица потока не дает ответ.
Название |
---|
Сейчас проходил у меня только поток.
в таком случае нужно поздравить тимус с фэйлом и ждать справедливого режаджа, который, почему-то, не случился вовремя
например вот 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 в матрице)