dcordb's blog

By dcordb, history, 6 years ago, In English

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?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Good day to you,

This problem is almost similar to this one (yet lower constraints). You can find the tutorial there too. Simply consider the edges of the graph to be princesses!

Good Luck & Have Nice Day!

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Yeah is the same problem, thank you.