cp3.5

# -*- coding: utf-8 -*-
"""
Created on Thu Apr 17 12:40:57 2014

@author: Administrator
"""
import numpy as np
import heapq

def SPFA(G, s):
    head, edge = G
    p = np.empty_like(head)
    dist = np.empty(len(head))
    dist.fill(np.inf)
    dist[s] = 0
    deque = [s]
    used = np.empty_like(head, dtype=bool)
    used.fill(False)
    while len(deque):
        knot = heapq.heappop(deque)
        used[knot] = False
        nedge = head[knot]
        while nedge != -1:
            nknot = edge[nedge]['to']
            if dist[nknot] > dist[knot] + edge[nedge]['w']:
                dist[nknot] = dist[knot] + edge[nedge]['w']
                p[nknot] = knot
                if not used[nknot]:
                    heapq.heappush(deque, nknot)
                    used[nknot] = True
            nedge = edge[nedge]['next']
    return dist, p

def ford(G, s, t):
    def dfs(v, f):
        if v == t: return f
        used[v] = True
        for to, w in enumerate(G[v]):
            if not used[to] and w > 0:
                d = dfs(to, min(f, w))
                if d:
                    G[v,to] -= d
                    G[to,v] += d
                    return d
        return 0
    flow = 0
    while True:
        used = np.empty(len(G), dtype=bool)
        used.fill(False)
        f = dfs(s, np.inf)
        if f == 0: return flow
        flow += f
        
def mincostflow(cap, cost, s, t, f):
    res = 0
    nv = len(cap)
    dist = np.empty(nv)
    p = np.zeros(nv, dtype=int)
    used = np.empty(nv, dtype=bool)
    while f > 0:
        dist.fill(np.inf)
        dist[s] = 0
        used.fill(False)
        used[s] = True
        deque = [s]
        while len(deque):
            knot = heapq.heappop(deque)
            used[knot] = False
            for nknot, w in enumerate(cost[knot]):
                if w and cap[knot,nknot] and dist[nknot] > dist[knot] + w:
                    dist[nknot] = dist[knot] + w
                    p[nknot] = knot
                    if not used[nknot]:
                        heapq.heappush(deque, nknot)
                        used[nknot] = True
        d, v = f, t
        while v != s:
            d = min(d, cap[p[v],v])
            v = p[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            cap[p[v], v] -= d
            cap[v, p[v]] += d
            v = p[v]
    return res
            
    


if __name__ == '__main__':
#    G = np.array([[0,10,2,0,0],[0,0,6,6,0],[0,0,0,0,5],[0,0,3,0,8],[0,0,0,0,0]])
     
#    print ford(G,0,4)

#    G = (np.array([ 1,  5,  4,  6,  8,  9, 19]),
#         np.array([(1, 2.0, -1), (2, 5.0, 0), (2, 4.0, 10), (3, 6.0, 2), (3, 2.0, 12),
#                   (4, 10.0, 3), (5, 1.0, 14), (5, 3.0, 15), (6, 5.0, 7), (6, 9.0, 17),
#                   (0, 2.0, -1), (0, 5.0, -1), (1, 4.0, 11), (1, 6.0, -1),
#                   (2, 2.0, 13), (1, 10.0, -1), (3, 1.0, -1), (4, 3.0, 16),
#                   (4, 5.0, -1), (5, 9.0, 18)], 
#                  dtype={'names':['to','w','next'], 'formats':['<i4','<f8','<i4'], 'offsets':[0,8,16], 'itemsize':24, 'aligned':True}))
#    print SPFA(G, 0)

    cap = np.array([[0,10,2,0,0],[0,0,6,6,0],[0,0,0,0,5],[0,0,3,0,8],[0,0,0,0,0]])
    cost = np.array([[0,2,4,0,0],[0,0,6,2,0],[0,0,0,0,2],[0,0,3,0,6],[0,0,0,0,0]])
    cost -= cost.T
    f = 11
    print mincostflow(cap, cost, 0, 4, f)