| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
TL;DR version: You are given a bipartite graph with atmost 1000 vertices on each side. M (upto 1,000,000) edges are added one by one. Compute the minimum vertex cover after each addition.
Clarification: You need to compute the minimum vertex cover / maximum matching everytime an edge is added.
Any ideas?
Kőnig's theorem will definitely help
Obviously. However, the problem is that I cannot compute the maximum matching naively 1e6 times....
Maybe the trick is to effectively check (after adding each edge) whether there exists a new augmenting path. There will be no more than min(N, M) such paths, so we can afford running some calculations on the entire graph after finding each augmenting path. Author says, that his approach uses about 700kk operations, so this may be it.
"Maybe the trick is to effectively check (after adding each edge) whether there exists a new augmenting path"
This is what I'm seeking help on...
Ok, so just build a directed graph with one vertex representing all unmatched vertices in the first set (vertex A) and other one representing unmatched vertices in the second set (vertex B). Other vertices will correspond to pairs of matched vertices. Each unmatched edge in original graph connecting vertices a and b will translate to directed edge between a' and b', where v' is a vertex in new graph corresponding to original vertex v in the old graph. Direction of this edge will be from a' to b' if a was in the same set as A in our original graph and from b' to a' in the opposite case. The task now is to determine whether after adding new edge there exist a path from A to B.
I know one of the guys who solved that problem, lucasmelo, and he only solved it because I kept bothering him to help me with it, though you can see I still don't have an accepted in it = ).
If I remember correctly (I can't find our talk) he checks, when a new monster arrives, if it is covered by his choice of guards in the previous iteration, if it is our answer is the same from the previous iteration. Otherwise he runs the hopcroft-karp code from wikipedia and gets a new min vertex cover. I also think he did the problem backwards (going from all monsters to zero monsters) but I can't think now how he did that
I don't know if that was the intended solution as his time is way slower than the other guy time.