11183 - Teen Girl Squad

[Abednego]

There is a very simple and beautiful algorithm by Fulkerson:
http://www.springerlink.com/content/t628212211v86275/

[mf]

There is a very simple and beautiful algorithm by Fulkerson:
http://www.springerlink.com/content/t628212211v86275/

Could you outline it here?

[Abednego]

Could you outline it here?

Read the paper. :) It's very simple.

The basic idea is this. Suppose you wanted to find a good lower bound on the weight of the minimum rooted tree. Here is a good candidate. For each non-zero vertex, take the smallest incoming edge. Clearly, each vertex needs to have an incoming edge, and it can't be smaller than the smallest one.

If the resulting set of n-1 edges is already a tree, then we are done.Otherwise, there is only one thing that can happen - we get jellyfish. More precisely, we get a single tree rooted at zero and any number of graphs that look like trees, rooted at a cycle (what I call jellyfish).

The next step is to take each cycle and compress it into a single vertex, so we get trees instead of jellyfish. If you spend 10 minutes thinking about what it means to compress a cycle into a vertex in this case, you'll see that we'll need to change the weights of all the edges that enter the cycle. The change is very simple - their weights will decrease by the weight of the edge we are currently using at the entrance vertex.

After we compress cycles, we simply start over, only this time, we have strictly fewer vertices.

The paper is pretty short and explains this well.

[mf]

Actually, I think that's exactly the same algorithm everyone here is using
The first google hit for directed mst calls it Chu-Liu/Edmonds' algorithm, though.

Read the paper. It's very simple.

The link you've posted asks me to pay $32

[Abednego]

The link you've posted asks me to pay $32 :(

Ah. Evil Springer. I can get it from my university's computers. If you send me a private message with your email address, I'll email you the paper.

[To anyone from Springer reading this: Of course I'm joking. I would never try to distribute and publicise research done over 30 years ago that you managed to grab the rights to. That wouldn't be very professional of me, and would hurt the scientific community.]

[fh]

Does the paper talk about the implementations?

When the jellyfish is compressed into a single vertex, the will be many parallel edges go in/out from that vertex. We should keep the minimum one to keep the graph simple. However, the graph is now changed.

It's fortunate that in this problem (11183) only asks the minimum weight of the directed MST. How about If we are asked which edges from the original graph belong to the directed MST, it would be much harder. Isn't it? How do we keep track the original edges when compressing the jellyfish? Does the paper talk about it?

[Abednego]

It would not be much harder. The trick is to do the compression using Union/Find. Then you don't even need to change the graph. After you compress, whenever you see an edge (u, v), you simply treat it as an edge (Find(u), Find(v)).

[fh]

It would not be much harder. The trick is to do the compression using Union/Find. Then you don't even need to change the graph. After you compress, whenever you see an edge (u, v), you simply treat it as an edge (Find(u), Find(v)).

IMHO, using union/find does not keep the graph unchanged since to compress the jellyfish, the incoming edges' weight must be reduced for the resulting vertex. (or there is a trick to avoid altering the edges' weight?)

After that, if there is a change of selected incoming edge for that vertex it becomes more confusing to update. It's easy to calculate Find(u) = x, but to update the edge in the "original" graph, we need the inverse Find(x) to get back the u and other possible vertices..

Does anyone here got AC without changing the graph? and able to give one of the possible Directed MST graph (the selected d-mst edges from the input)?[/b]

[s000015]

My program yielded correct result for test cases above,
but I still got WA...

Here is some random test cases:

Code: Select all

15
4 14
3 1 4
3 1 3
3 2 3
3 2 6
1 3 9
3 1 5
2 0 9
0 1 8
0 2 8
3 1 2
2 1 3
1 3 7
1 3 5
1 0 1
4 17
3 0 6
3 0 3
1 2 8
2 3 4
0 1 4
0 1 3
3 2 7
3 1 4
1 2 2
1 0 8
0 2 3
3 1 3
3 2 6
3 2 2
3 1 0
3 0 7
3 1 0
4 18
0 2 0
3 2 3
3 2 4
3 2 8
3 2 2
0 1 8
1 2 2
0 1 3
1 3 8
3 0 2
0 2 6
0 2 0
1 3 0
2 3 9
1 0 5
0 3 8
1 2 0
0 2 4
5 19
4 3 1
1 0 4
3 4 7
4 2 6
4 0 6
3 0 2
0 2 4
2 3 9
0 1 7
4 2 2
1 0 7
2 3 2
4 2 5
2 3 7
1 2 2
3 4 6
3 4 6
1 0 6
1 2 9
5 22
1 4 6
4 1 5
3 0 9
0 4 8
1 3 1
1 3 7
1 4 9
4 0 2
3 0 9
4 0 2
1 0 8
3 2 9
1 0 1
3 2 6
0 3 9
2 4 4
1 4 3
0 1 0
1 3 2
3 2 3
3 1 0
4 2 9
5 24
3 0 3
2 1 2
1 0 7
0 3 6
3 0 9
2 4 0
0 1 9
3 0 4
1 4 2
3 2 3
2 0 3
1 4 9
2 0 9
3 4 1
1 0 0
1 0 7
4 0 1
3 0 2
0 1 0
0 1 1
4 1 4
3 4 0
1 0 4
0 2 5
5 27
2 0 6
2 0 3
1 4 6
3 4 0
3 0 2
0 1 8
0 4 1
1 0 0
3 0 9
3 2 0
2 0 2
3 2 4
3 0 5
2 4 4
4 1 8
0 3 9
4 0 8
2 3 4
4 3 7
0 1 8
4 0 4
1 2 0
0 3 0
2 1 3
0 4 2
3 1 5
4 0 0
5 30
1 3 5
1 2 4
4 0 6
4 3 3
2 3 2
1 2 1
0 2 6
3 0 9
3 1 4
4 3 9
0 3 4
1 3 3
3 1 5
1 4 5
0 2 7
4 3 8
2 0 5
2 4 3
3 4 7
1 0 6
4 2 1
0 2 4
2 3 8
1 0 1
0 1 6
4 2 0
4 2 3
3 1 6
4 3 7
4 1 6
5 32
1 2 2
3 0 3
3 4 4
0 4 6
4 0 8
1 3 1
3 0 5
4 0 3
2 4 9
0 4 4
0 4 1
3 0 9
0 3 4
4 0 5
2 3 4
1 2 2
1 3 2
0 4 2
4 3 9
2 4 0
3 4 7
0 3 2
0 2 6
2 4 9
1 4 7
4 3 7
1 4 5
3 2 3
2 3 1
0 1 4
3 4 8
4 0 3
5 32
1 4 7
0 1 8
4 0 8
1 2 7
2 3 6
3 4 0
1 2 8
1 4 6
3 0 8
3 4 7
4 1 9
4 2 1
1 2 1
1 0 4
3 2 2
4 1 9
2 0 5
0 2 8
3 1 0
0 2 2
4 1 9
4 0 5
2 0 0
2 3 7
2 1 4
0 2 1
0 2 8
1 2 6
0 3 8
3 1 3
3 0 4
2 4 5
5 36
3 2 0
0 1 9
3 0 3
4 3 8
0 1 0
0 2 4
4 0 9
3 4 9
4 2 2
2 1 5
1 2 1
1 2 9
4 0 2
2 0 0
2 4 3
2 0 2
0 2 0
3 0 3
3 4 1
1 0 2
3 2 6
3 1 4
4 2 4
1 2 2
3 1 8
3 0 1
2 3 4
4 0 1
3 2 0
4 2 2
2 0 7
0 2 5
1 2 2
2 1 6
2 4 8
2 3 7
5 40
2 4 5
1 3 4
0 3 8
4 2 5
3 4 6
4 3 4
0 2 8
0 2 0
1 0 5
4 1 6
3 2 6
1 2 4
0 1 2
4 1 9
3 4 8
4 1 4
4 0 1
4 3 5
1 0 0
4 3 6
4 2 8
0 2 4
4 2 9
1 0 3
4 2 1
3 0 8
2 4 1
4 2 6
0 4 9
4 2 3
3 2 4
4 0 2
1 4 7
1 4 4
0 4 5
3 4 5
3 4 1
4 3 2
3 4 9
0 3 7
5 40
4 3 5
3 2 2
0 1 0
1 3 3
4 0 0
2 1 4
2 3 4
4 2 3
3 4 3
0 3 4
2 3 8
0 2 7
1 3 2
2 4 8
0 1 1
0 3 3
2 4 5
3 4 3
3 2 5
4 2 8
1 3 2
1 2 5
0 4 4
3 1 1
4 2 7
2 4 3
3 0 0
2 1 6
3 1 7
1 4 1
0 1 9
3 1 4
0 1 3
0 2 6
2 4 6
2 4 2
1 4 6
2 3 8
2 0 7
0 2 2
5 44
3 0 7
0 2 8
4 0 5
1 3 9
4 3 1
1 2 6
4 0 9
0 3 1
2 4 3
0 2 1
4 2 6
2 1 0
3 4 1
1 2 7
2 0 2
2 1 9
4 0 8
0 2 6
2 3 1
3 2 9
2 3 0
2 1 1
2 3 0
2 4 7
3 2 5
1 4 8
4 3 7
4 0 0
2 1 7
3 2 4
3 2 3
2 3 3
2 3 9
0 2 0
1 0 0
3 1 0
0 3 8
1 3 7
1 3 3
2 3 4
0 4 3
2 1 9
4 1 3
2 0 0
5 44
4 0 2
0 4 4
0 3 5
2 3 6
1 2 6
2 3 5
4 1 2
0 2 8
1 2 7
4 2 5
1 3 6
0 2 2
1 3 3
0 4 2
4 2 2
1 2 0
1 4 7
4 0 5
4 2 4
3 1 5
2 1 5
4 2 7
0 1 6
2 3 2
2 0 8
4 3 0
3 0 0
1 0 1
3 0 7
0 1 2
2 3 9
1 2 4
0 4 3
0 3 6
3 1 6
3 0 7
1 4 8
0 1 2
4 0 2
1 0 2
3 4 9
0 2 5
2 3 8
0 4 9

Output:

Code: Select all

Case #1: 16
Case #2: 7
Case #3: 3
Case #4: Possums!
Case #5: 7
Case #6: 9
Case #7: 3
Case #8: 13
Case #9: 7
Case #10: 7
Case #11: 5
Case #12: 5
Case #13: 5
Case #14: 1
Case #15: 4

Is this correct?

My code:http://phpfi.com/211399

Sorry for my poor English..

[mf]

My accepted program produces this output:

Code: Select all

Case #1: 16
Case #2: 7
Case #3: 3
Case #4: 17
Case #5: 7
Case #6: 9
Case #7: 3
Case #8: 12
Case #9: 7
Case #10: 7
Case #11: 5
Case #12: 5
Case #13: 5
Case #14: 1
Case #15: 4

[s000015]

Thank you

I got ac.

Here is some more test cases:

Code: Select all

4
0
0
1
0
3
0
3
2
1 2 999
2 1 999

Code: Select all

Case #1: 0
Case #2: 0
Case #3: Possums!
Case #4: Possums!

[SRX]

sorry , I have passed the all test cases above ,
can someone give me some test cases ?

thanks

[little joey]

Now that I finally solved this problem, after reading everything that is publicly accessible (not a lot, both quantitative and qualitative), I would really like to read Fulkerson's article. Sure, I don't want to pay 32 bucks, and I also don't want to invite anyone to doing something illegal. But if anyone who accidentally knows my email address would accidentally attach it to an email and accidentally drop that mail into my inbox, that wouldn't be considered theft, would it?

BTW. Does the fact that Springer owns the rights to this article automatically mean that they got the intellectual rights to the algorithm described in it? So if I would make a description of the algorithm and put it on my web site, would I then be prosecutable? And if I use it to solve this problem? And if I incorporate it in a software product that I exploit commercially?

[RoBa]

I wonder the time complexity of the ACed algorithm. I got TLE with an O(V^3) implementation, and finally AC with an ugly O(VE).

And I agree with fh: If we are asked which edges from the original graph belong to the directed MST, it will be much harder. Could someone please show me an implementation about it? I can't understand why Union-Find will work...