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 - 105 and 105
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?
