Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
PyCPXで最大流問題を解く
# -*- 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.]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment