An interesting graph problem

Revision en1, by dcordb, 2017-10-29 21:07:28

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?

Tags graphs, constructive algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dcordb 2017-10-29 21:07:28 1187 Initial revision (published)