Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

マトリョーシカ

マトリョーシカはロシアの民芸品として有名な人形である．
マトリョーシカは上下に分割でき，開くと中により小さい別の人形が入っている．
現れた小さい人形を開くとさらに小さい人形が入っている，というような入れ子構造になっている．

あなたは旅行先で珍しい形のマトリョーシカを見つけ，N 体の人形を購入した．
i 番目の人形の形状は，xi &times; yi &times; zi の直方体である．

ひとしきりマトリョーシカを鑑賞したあなたは，マトリョーシカを仕舞おうとしている．
その前に，いくつかの人形を別の人形に格納することによって必要なスペースを減らしたい．
人形を格納する際には，まだ中にひとつも人形を格納していない人形にだけ，他の人形をひとつ格納できる．
ただし，直接的に格納される人形についてだけ数えるものとし，中に人形が入っている人形を別の人形に格納することはできる．

収納された人形は，外部から見えない状態になる．
ただし，以下の条件を満たさなければならない．

 人形は回転してよいが，直方体のそれぞれの辺は，他方の直方体のいずれかの辺に平行

 回転後，対応する辺同士の長さそれぞれについて，収納される側の人形の長さの方が短い

 1 個の人形の中に直接収納できる人形の数は高々 1 個

押入れの容積は限られているので，外部から見えている人形の体積の和を最小化したい．
あなたの仕事は，人形を収納する操作を任意の回数繰り返して達成できる，外部から見えている人形の体積の和の最小値を求めるプログラムを作成することである．

Input

入力は複数のデータセットからなる．
データセットの個数は最大でも 50 個を超えない．
各データセットは次の形式で表される．

N
x1 y1 z1
:
:
xN yN zN

各データセットは N + 1 行からなり，データセットの 1 行目には，人形の数を表す整数 N が与えられる．
続く N 行の内 i 行目には，i 番目の人形の大きさを表す 3 つの整数 xi, yi, zi が半角スペース区切りで与えられる．
これらの整数は，1 ≤ N, xi, yi, zi ≤ 100 を満たす．

入力の終わりは 1 つのゼロからなる行で表される．

Output

各データセットについて，外部から見えている人形の体積の和の最小値を 1 行で出力せよ．

Sample Input

2
1 2 3
4 2 3
3
2 5 2
3 3 4
5 5 5
5
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
5
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
10
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 4
3 3 8
3 2 7
0

Output for Sample Input

24
145
125
15
864



Sample input:
2
1 2 3
4 2 3
3
2 5 2
3 3 4
5 5 5
5
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
5
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
10
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 4
3 3 8
3 2 7
0


Sample output:
24
145
125
15
864

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

def solve():
    N = int(readline())
    if N == 0:
        return False
    P = []
    for i in range(N):
        *p, = map(int, readline().split())
        p.sort()
        P.append(p)
    mcf = MinCostFlow(2*N+2)
    P.sort()
    su = 0
    for i in range(N):
        xi, yi, zi = P[i]
        for j in range(i):
            xj, yj, zj = P[j]
            if xi > xj and yi > yj and zi > zj:
                mcf.add_edge(2*j+1, 2*i, 1, -xj*yj*zj)
        su += xi*yi*zi
        mcf.add_edge(2*i, 2*i+1, 1, 0)
        mcf.add_edge(2*N, 2*i, 1, 0)
        mcf.add_edge(2*i+1, 2*N+1, 1, 0)
    ans = su
    for i in range(N):
        f = mcf.flow(2*N, 2*N+1, 1)
        su += f
        ans = min(ans, su)
    write("%d\n" % ans)
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
import heapq

class MinCostFlow:
    class Edge:
        def __init__(self,to,cap,rev,cost):
            self.to = to
            self.cap = cap
            self.rev = rev
            self.cost = cost

    def __init__(self,n,inf=1000000007):
        self.n = n
        self.inf = inf
        self.e = [[] for _ in range(n)]

    def add_edge(self, fr, to, cap, cost):
        self.e[fr].append(self.Edge(to,cap,len(self.e[to]),cost))
        self.e[to].append(self.Edge(fr,0,len(self.e[fr])-1,-cost))

    def compute(self,source,sink,f):
        res = 0
        h = [0]*self.n
        prevv = [0]*self.n
        preve = [0]*self.n
        while (f > 0):
            pq = []
            dist = [self.inf]*self.n
            dist[source] = 0
            heapq.heappush(pq,(0,source))
            while pq:
                cost, v = heapq.heappop(pq)
                cost = -cost
                if dist[v] < cost:continue
                for i, edge in enumerate(self.e[v]):
                    if edge.cap > 0 and dist[v] - h[edge.to] < dist[edge.to] - edge.cost - h[v]:
                        dist[edge.to] = dist[v] + edge.cost + h[v] - h[edge.to]
                        prevv[edge.to] = v
                        preve[edge.to] = i
                        heapq.heappush(pq,(-dist[edge.to],edge.to))
            if dist[sink] == self.inf:return -1
            for v in range(self.n):
                h[v] += dist[v]

            d, v = f, sink
            while v != source:
                d = min(d,self.e[prevv[v]][preve[v]].cap)
                v = prevv[v]
            f -= d
            res += d*h[sink]
            v = sink
            while v != source:
                self.e[prevv[v]][preve[v]].cap -= d
                self.e[v][self.e[prevv[v]][preve[v]].rev].cap += d
                v = prevv[v]
        return res

def less(a,b):
    for i in range(3):
        if b[i]<=a[i]:return False
    return True

def main():
    while True:
        n = int(input())
        if n==0:break
        a = []
        MCF = MinCostFlow(n+n+2)
        s = n+n
        t = s+1
        summ = 0
        for i in range(n):
            x = list(map(int,input().split()))
            x.sort()
            a.append(x)
            summ+=(x[0]*x[1]*x[2])
        for i in range(n):
            for j in range(n):
                if i == j:continue
                if less(a[i],a[j]):
                    MCF.add_edge(i,j+n,1,-(a[i][0]*a[i][1]*a[i][2]))
        for i in range(n):
            MCF.add_edge(s,i,1,0)
            MCF.add_edge(i+n,t,1,0)
        MCF.add_edge(s,t,MCF.inf,0)
        print (summ+MCF.compute(s,t,MCF.inf))

if __name__ == '__main__':
    main()