PyCPXで最大流問題を解く

pycpx_max_flow.py

# -*- coding: utf-8 -*-

import numpy as np
from pycpx import CPlexModel

# 入力（有向グラフ，頂点は0-index）
# n m
# s_1 t_1 c_1
# s_2 t_2 c_2
# ...
# s_m t_m c_m

n, m = map(int, raw_input().split())

model = CPlexModel()
f = model.new(m) # f[i] = 辺 i のフロー
incoming = [[] for i in xrange(n)] # imcoming[i] = 頂点 i から出て行く辺の番号のリスト
outgoing = [[] for i in xrange(n)]
for i in xrange(m):
        s, t, c = map(int, raw_input().split())
        model.constrain(0 <= f[i] <= c)
        incoming[s].append(i)
        outgoing[t].append(i)

for i in xrange(1, n - 1):
        incoming_sum = sum(f[j] for j in incoming[i])
        outgoing_sum = sum(f[j] for j in outgoing[i])
        model.constrain(incoming_sum == outgoing_sum)

flow = sum(f[j] for j in incoming[0])
print model.maximize(flow)
print model[f]

# 4 5
# 0 1 2
# 0 2 1
# 1 2 1
# 1 3 1
# 2 3 2
# ->
# 3.0
# [ 2.  1.  1.  1.  2.]