| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
Hello!
I'm trying to understand how the algorithm for finding the minimum path cover in DAG works. I read the description from here: http://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph . Can someone explain to me the idea behind this algorithm and why it outputs the right answer?
The phrase "to split a DAG into paths" means "to leave at most one incoming and one outcoming edge for each vertex".
If we add an edge to the answer, we merge two paths into one.
Maximum matching algorithm tries to take as many edges as possible, while not violating the rule of one incoming and one outcoming edge.
And that's all.
But why "to split a DAG into paths" means "to leave at most one incoming and one outcoming edge for each vertex"? For instance, in the second graph from this page http://stackoverflow.com/questions/10783473/minimum-path-cover-in-directed-acyclic-graph there are more incoming and outcoming edges for a vertex for the path 1-2-3-4-5.
Every node should belong to exactly one path. Initially there N one-node paths. The more edges you add, the less paths you will get eventually.
You contradict yourself. By definition, a directed path is a sequence of edges where each pair of consecutive edges share a vertex and all edges have the same direction.
And I'll remind you that in the problem we're discussing now we cover the DAG with vertex-disjoint paths. Covering a DAG with edge-disjoint paths is much easier in fact (it's solvable by a greedy algo).
Can you describe the solution in case when paths are edge-disjoint more detailed?
This problem is too easy for you to solve it yourself :).
Cool! You're right, that's really simple.
This is correct for the case when you want to cover all the edges of the DAG with edge-disjoint paths. I thought that you were referring to the original requirement, i.e. cover all the nodes of the DAG, but with edge-disjoint paths. Anyway, this version of the problem is also solvable — my idea uses max-flow with lower capacities in the nodes of the DAG + binary search.
could you please explain more the greedy solution to problem of the edge — disjoint paths ?
Let's take an arbitrary vertex v and look at all of its incoming edges. We know that all of them will lie on some paths (we don't care about where will these paths start and how do they really look like). So, vertex v has degin[v] incoming paths. Now we want to continue some of them. For this purpose we can use edges that come out from vertex V, and continue incoming paths in arbitrary way. Now we have two cases:
That's all.
Maybe this could be useful:
http://code.google.com/codejam/contest/dashboard?c=204113#s=a&a=2
(: