Need Help on Bipartite Matching problem with 2 types of weight

Revision en2, by gamegame, 2018-03-25 19:47:47

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!

Tags bipartite matching

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English gamegame 2018-03-25 19:47:47 71
en1 English gamegame 2018-03-25 19:37:52 523 Initial revision (published)