A contest on max flow and matching related algorithms will start within 1 hr. There is be 6 problems. Link: http://lightoj.com/practice_contest_index.php?contest_id=88
EDIT: contest duration has been extended to 24 hrs. You are invited to join. :)
A contest on max flow and matching related algorithms will start within 1 hr. There is be 6 problems. Link: http://lightoj.com/practice_contest_index.php?contest_id=88
EDIT: contest duration has been extended to 24 hrs. You are invited to join. :)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
I was unable to understand the statements without some guessing :(. Problem statements contains lots of grammar & vocabulary mistakes (e.g. shouldn't A's title be "Fed Up With Teaching" ?).
Can anybody tell me how to solve "D — Dark Time for Dark Wizard"? I have used Min-Cost-Max-Flow, but my graph was wrong. The main problem is edges are bidirectional, and we can use them at most once.
Split the edges and run Min-Cost-Max-Flow. By splitting the edges I mean, treat each edge as a different one, insert a new node within the edge for every edge.
Can you please describe it on example, or more precisely. I have added two vertices for each edge, if we have edge between A and B with cost X, my program adds two vertices C and D, and the edges (start, end, cap, cost) : (A, C, 1, X) (B, C, 1, X) (D, A, 1, 0) (D, B, 1, 0) (C, D, 1, 0), but this graph has negative cycles.
Suppose there are two edges between A and B with cost 3 and 5. If you split these two edges with node C, D then it'll look like this, (start, end, cap, cost) : (A, C , 1 , 3), (C, B , 1 , 0), (A, D , 1 , 5), (D, B , 1 , 0). These edges are bidirectional. Now if we run min-cost-max-flow on a bidirectional graph, we'd get maximum amount of death eater each with shortest path to voldemort.
Are you solved this problem? edges are bidirectional. Your example is wrong, because we have not possibility to go from B to A. Use only one edge (A, B) in your future example please.
Yes, I've solved the problem. If there was no multiple edges in this problem, this would've been a straight forward min-cost-max-flow solution. Since there can be multiple edges between any two nodes, I've split the edges and ran min-cost-max-flow. If you want I can show you my code.
Yes, please. Show me your code.
Check your PM.
Can anybody write editorial for this contest? That will be great. Thanks
Can anybody write editorial for this contest? That will be great. Thanks.