gamegame's blog

Need Help on Bipartite Matching problem with 2 types of weight
By gamegame, history, 7 years ago, In English

I have seen a problem about bipartite matching on a special weighted graph and i would like to know the solution. The graph is similar to 875F - Royal Questions where nodes in one sides have at most 2 neighbours and the weight of these two edges are the same. However, each edge has 2 weights Ai and Bi, and the total weight is (sum of A)*(sum of B). The task is to find a maximum matching with highest total weight. N<=10000 and A,B<=30 where N is the number of nodes. Could someone give hints/solutions about this problem? Million thanks!

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

Comments Comments (8)
| Write comment?
»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Auto comment: topic has been updated by gamegame (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Let's find optimal sum with weights of right part = 0, and optimal sum with weights of left part = 0.

Answer is sumA * sumB

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Could you elaborate more about that = 0? Do you mean that you set every Bi to 0 then find max sumA? Thanks

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Yes

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        How about this. Your method: (3+2)*(3+2) = 25 while max weight = (3+2)*(3+1) = 20Graph

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

          Oh, sorry, i thought that each vertex has a weight, not an edge.

          → Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

This problem is basically Time is Money with matching instead of spanning tree I think

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I think this comment is incorrect, can someone clear this up?

    That trick works for Time is Money because in that problem we want to minimize and the shape being convex means that the first point that lies outside of that shape is in the border of the convex hull, but here we want to maximize so the same doesn't apply.

    → Reply