11183 - Teen Girl Squad

[sunny]

got so many WAs on this problem.
any test cases plz.

[sclo]

This is the directed minimum spanning tree problem.

[arsalan_mousavian]

This is the directed minimum spanning tree problem.

during the contest i have figured out that the problem could be solved with MST, but i have one problems, is it enough to start MST algorithm from the vertex which indegree is 0, or it has some blind spots?
thanks in Advance...

[Hadi]

For this problem, using "Prim" or "Kruskal" is not correct. they are for undirected graphs. you can find a counter-example easily if you try.

You should use Chu,Liu/Edmonds algorithm to solve this problem. for a brief description see http://www.ce.rit.edu/~sjyeec/dmst.html

But implementing it they way "what it says" will time out. (As our solution timed out during the contest)

Could anybody please give some hints on efficient implementations?

[Monsoon]

For this problem, using "Prim" or "Kruskal" is not correct. they are for undirected graphs. you can find a counter-example easily if you try.

You should use Chu,Liu/Edmonds algorithm to solve this problem. for a brief description see http://www.ce.rit.edu/~sjyeec/dmst.html

But implementing it they way "what it says" will time out. (As our solution timed out during the contest)

Could anybody please give some hints on efficient implementations?

hmm, i have question to step 3. of this algo, i think that is sufficent to use this equation c(i,k)=c(i,j)-(c(x(j),j), but i've WA, anyone could show me why we must substract min_{j}(c(x(j),j)) ?

[sclo]

min_{j}(c(x(j),j)) is a constant on each cycle, so I don't see why we even need that term either.
I'm just getting TLE.

(edit)
Never mind, i'm getting tle because a bug in my code for breaking cycles turns my program into an infinite loop.

After many many WA, I finally got AC
It is not necessary to consider use the term min_{j}(c(x(j),j)) to reassign edge weights. But it is necessary to reassign edge weights, my previous code forgot to do so and it got me many WA.

Heres some testcases:

Code: Select all

8
4
4
0 1 5
0 2 6
1 3 5
2 3 1
9
16
0 1 4
0 2 4
1 2 1
1 3 2
2 1 1
3 4 1
3 5 3
4 2 2
4 3 1
5 6 1
5 7 2
6 4 3
6 5 1
7 8 1
8 7 1
8 6 2
6
11
0 1 10
0 2 10
0 5 5
1 2 8
5 1 2
2 4 6
3 2 4
3 1 7
4 3 3
4 5 3
5 3 9
6
11
0 1 1
0 2 10
0 5 5
1 2 8
1 5 2
2 4 6
3 2 4
3 1 7
4 3 3
5 4 11
5 3 9
2
1
0 1 10
2
1
1 0 10
4
4
0 1 10
0 2 10
1 3 20
2 3 30
4
4
0 1 10
1 2 20
2 0 30
2 3 100

Output:

Code: Select all

Case #1: 12
Case #2: 15
Case #3: 24
Case #4: 20
Case #5: 10
Case #6: Possums!
Case #7: 40
Case #8: 130

[fh]

Can somebody explain the meaning of pseudo-node?
Is pseudo-node achieved by replacing the nodes in the cycle into one node?

I tried to update the weight of all incoming edges to the cycle and then pick the smallest one and replace to it. However, my attempt to eliminate a cycle leads to creating another cycle! This is one of the case:

1
7
9
1 2 1
2 3 1
3 1 1

4 5 1
5 6 1
6 4 1

4 2 2
3 6 2
0 3 1000

There are two cycles after step 1, and after 3 attempts to eliminate cycles, it will create another cycle when eliminating the cycle itself.

Do we need to check whether the replacement edge should not lead to another cycle? because this checking step is not mentioned in the algorithm. Am I missing something?

[mf]

Can somebody explain the meaning of pseudo-node?
Is pseudo-node achieved by replacing the nodes in the cycle into one node?

Yes.
Technically, you can implement it with a union-find structure, like in Kruskal's algorithm.

There are two cycles after step 1, and after 3 attempts to eliminate cycles, it will create another cycle when eliminating the cycle itself.

Which you can then again successfully contract into a single vertex.

[sclo]

My testcase #2 requires the algorithm to break cycles 3 times.

[fh]

My testcase #2 requires the algorithm to break cycles 3 times.

I passed your testcase, but the testcase I mentioned above gives me headache. If you draw it, it'll go like this:

Code: Select all

Graph:

0    +--> 2 <-- 4 ---+
|    |    |     ^    |
|    |    v     |    v
|    1 <- 3 --> 6 <- 5
|         ^
|         |
+---------+

Edge cost from node 0 to 3 is 1000, the rest are 1.


Step 1, select minimum incoming arc for each node except root:

0    +--> 2     4 ---+
     |    |     ^    |
     |    v     |    v
     1 <- 3     6 <- 5

Step 2, break cycle 4-5-6:

0    +--> 2     4 ---+
     |    |     ^    |
     |    v     |    v
     1 <- 3 --> 6    5

Step 3, break cycle 1-2-3:

0         2 <-- 4 ---+
          |     ^    |
          v     |    v
     1 <- 3 --> 6    5

Step 4, break cycle 2-4-6-3:

0    +--> 2     4 ---+
     |    |     ^    |
     |    v     |    v
     1 <- 3 --> 6    5

Now, does this graph rings a bell?
It's the same as step 2 above!
Now, it's an endless loop.

How to avoid this?

[mf]

When you detect that there's a cycle, you should merge all vertices of the cycle into one, and replace any edges entering a vertex in the cycle by edges pointing to that new big one vertex.

Thus, in your example after steps 2 and 3, you will have three vertices: 0, {4,5,6} and {1,2,3}.
In step 4, merge vertices {1,2,3} and {4,5,6} into {1,2,3,4,5,6}.

[fh]

When you detect that there's a cycle, you should merge all vertices of the cycle into one, and replace any edges entering a vertex in the cycle by edges pointing to that new big one vertex.

Thus, in your example after steps 2 and 3, you will have three vertices: 0, {4,5,6} and {1,2,3}.
In step 4, merge vertices {1,2,3} and {4,5,6} into {1,2,3,4,5,6}.

I tried that way, but it doesn't yield an optimal result for sclo's second test case:

Code: Select all

9
16
0 1 4
0 2 4
1 2 1
1 3 2
2 1 1
3 4 1
3 5 3
4 2 2
4 3 1
5 6 1
5 7 2
6 4 3
6 5 1
7 8 1
8 7 1
8 6 2

Here is the graph for that input:

   4      2      3      2
0 ---> 1 ---> 3 ---> 5 ---> 7
|      ^      ^      ^      ^
|      |      |      |      |
|      | 1    | 1    | 1    | 1
|      |      |      |      |
|  4   v   2  v   3  v   2  v
+----> 2 <--- 4 <--- 6 <--- 8


Step 1, assign minimum incoming edge to each vertex:

                         
0      1      3      5      7
       ^      ^      ^      ^
       |      |      |      |
       | 1    | 1    | 1    | 1
       |      |      |      |
       v      v      v      v
       2      4      6      8


union set: {0}, {1,2}, {3,4}, {5,6}, {7,8}

Step 2, resolve cycle {1,2}, {3,4}, {5,6}, {7,8}:
// question: is it allowed to resolve many cycles in one step?

          2             2
0      1 ---> 3      5 ---> 7
       ^      |      ^      |
       |      |      |      |
       | 1    | 1    | 1    | 1
       |      |      |      |
       |   2  v      |   2  v
       2 <--- 4      6 <--- 8


union set: {0}, {1,2,3,4}, {5,6,7,8}

Step 3, resolve cycle {5,6,7,8}:

          2      3      2
0      1 ---> 3 ---> 5 ---> 7
       ^      |             |
       |      |             |
       | 1    | 1           | 1
       |      |             |
       |   2  v          2  v
       2 <--- 4      6 <--- 8


union set: {0}, {1,2,3,4,5,6,7,8}

Step 3, resolve cycle {1,2,3,4}:

          2      3      2
0      1 ---> 3 ---> 5 ---> 7
|      ^      |             |
|      |      |             |
|      | 1    | 1           | 1
|      |      |             |
|  4   |      v          2  v
+----> 2      4      6 <--- 8

Terminates with cost = 16

Whereas the optimum result is 15:

   4      2      3      2
0----> 1 ---> 3 ---> 5 ---> 7
       |      |      |      |
       |      |      |      |
       | 1    | 1    | 1    | 1
       |      |      |      |
       v      v      v      v
       2      4      6      8

How do you get 15? Is the order of resolving cycle matters?

[mf]

Code: Select all

Step 3, resolve cycle {5,6,7,8}:

          2      3      2
0      1 ---> 3 ---> 5 ---> 7
       ^      |             |
       |      |             |
       | 1    | 1           | 1
       |      |             |
       |   2  v          2  v
       2 <--- 4      6 <--- 8

No, no, no.
Vertices 5,6 and 7,8 were previously already bound together in deeper cycles. Instead of "resolving cycle {5,6,7,8}", you actually should be
dealing with the cycle {{5,6}, {7,8}}. You can resolve it by adding an edge from {5,6} to {7,8} (that'll be 5->7 of cost 2), and then resolve each of cycles {5,6} and {7,8} separately.

The whole point of this cycle contraction is that you can contract cycles each into a single vertex, reweight some edges, find directed MST of the new graph (try to draw this graph, that'll help you to understand the idea), and then get back at your original graph by expanding the cycles and deleting one of their edges. (But the problem statement doesn't ask you to find the edges of MST, so you can skip the last step in your code.)

[fh]

Ok I got it Accepted. Thanks sclo for the sample cases and mf for the explanation.

I miss the fact that return -1 can happen not only when step 1 fails but also when it fails in resolving cycles. I added a simple check and got Accepted.

This is the input that have no solution that I missed:

7 8
1 2 1
2 3 1
3 1 1

4 5 1
5 6 1
6 4 1

4 2 2
3 6 2

Output should be "Possums!"

[sclo]

Alternatively, you can do a dfs at the beginning to determine whether each node is reachable from the starting node. If they are all reachable, then the algorithm guarantees it will always find the minimum spanning tree.