Confused101's blog

Minimum sum of distances.
By Confused101, history, 8 years ago, In English

Given N points in one set(S1) and M points in another set(S2), Choose some edges between points from Set S1 to set S2 such that sum of edges(distances) is minimum and every vertex is chosen atleast once.

Can someone help me solving this problem. Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is exactly minimum-cost maximal flow problem.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to satisfy "every vertex is chosen at least once"?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Instead of infinite edge for vertex you use one infinite edge and one edge with capacity 1 and const -BIG. After that, you'll add BIG*vertices to the answer

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If set 2 doesn't have more numbers than set 1 then, Setting capacity of edges of source to set 1 and set 1 to set 2 equals to 1 and Setting capacity of edges from set 2 to sink to infinity should work. right?

        → Reply