| Optimal Marriage On Planet X |
In the classical marriage problem on Earth, you are given n men, n women, plus a compatibility rating for each pair of man and woman (higher means more compatible). You have to find the optimal pairing (i.e. a marriage), n disjoint pairs of men and women, such that the sum of the compatibility ratings for the formed pairs (marriages) is maximum. Typically, this is solved using maximum bipartite matching algorithms such as the Hungarian Method, or network flow algorithms.
Unfortunately, it is not so easy on planet X, because there are 3 sexes/genders instead of 2 :-) !!! The 3 sexes are Xelox,Yakki, and Zabra. You are given n Xeloxes, nYakkis, and n Zabras, and a set of compatibility ratings, r(x,y,z) for each triple (x,y,z) where x is a Xelox, y is a Yakki, z is a Zabra. In this problem, you have to form n disjoint triples, such that the sum of their compatibility ratings is maximal. Since the aliens on planet X do not want their compatibility ratings to be too similar, for any two different compatibility ratings r1, and r2, it is guarranteeed that 300*abs(r1-r2) > (r1+r2) .
There is a number of inputs. Each input begins with n (n < 21). n3 lines follow; each of the form:
x y z r
where x is the index of a Xelox, y is the index of a Yakki, z is the index of a Zabra, and 0 < x,y,z < n+1. r is the compatibility rating, r(x,y,z) of this triple. r fits inside an unsigned 32 bit integer.
For each input, output the maximum sum of the compatibility ratings after forming the optimal triples (marriages) on a single line.
2 1 1 1 0 1 1 2 0 1 2 1 0 1 2 2 9 2 1 1 9 2 1 2 0 2 2 1 0 2 2 2 0
18