Hi.

This problem is from a Mexican Training Camp of this year, you can find it here (spanish only). The following is the abridged statement:

Given a undirected, simple and weighted graph with N nodes and M edges you should select a set of exactly N edges (you throw away the other M - N edges) and direct each of them, such that the sum of weights will be maximum, with the restriction that each node must have out-degree equal to 1 in this new directed graph; or say that there is not solution.

Constraints:

• 3 ≤ N ≤ 10000

• 3 ≤ M ≤ 50000

• The weight of edges is between  - 10⁵ and 10⁵

Example:

4 6 
1 2 1 
1 3 -2 
2 3 4 
1 4 -8 
2 4 16 
3 4 -32

In this case the answer is 19, you can direct edges the following way:

• 4 to 2 (weight = 16)

• 2 to 1 (weight = 1)

• 1 to 3 (weight = -2)

• 3 to 2 (weight = 4)

I thought about flow but is not clear how I would do the graph, I also thought that N - 1 edges will be from the maximum spanning tree but that is wrong as well. Anyway could you help me?