def minMeanCycle(G_in, G_out, f, b, c):
    """ input: graph G, with arc flow, f, arc capacity b and arc cost c.
       output: a cycle in the residual graph of minimal mean cost
       assumes graph is connected and contains at least one vertex
       algorithm by Dick Karp from 1976
       complexity is O(n*m) where n is the number of nodes and m the number of arcs
   """
    V = G_out.keys()
    n = len(V)
    s = V[0]
    POSINFTY = float('inf')
    NEGINFTY = -float('inf')
    d = {(0, s): 0}
    p = {(0, s): s}
    for k in range(1, n + 1):
        for v in V:
            for u in G_in[v]:
                if (k - 1, u) in d:
                    alt = d[k - 1, u] + c[u, v]
                    if (k, v) not in d or d[k, v] > alt:
                        d[k, v] = alt
                        p[k, v] = u
    min_v = POSINFTY
    argmin_v = s
    for v in V:
        max_k = NEGINFTY
        for k in range(n):
            if (n, v) in d and (k, v) in d:
                alt = (d[n, v] - d[k, v]) / float(n - k)
                if max_k < alt:
                    max_k = alt
        if min_v > max_k and max_k > NEGINFTY:
            min_v = max_k
            argmin_v = v
    if min_v == POSINFTY:
        return None
    print('argmin_v=' + str(argmin_v))
    print('d       =' + str(d))
    print('p       =' + str(p))
    cycle = []
    j = {}
    v = argmin_v
    for i in range(n, 0, -1):
        u = p[i, v]
        j[v] = len(cycle)
        cycle.append((u, v))
        if u in j:
            cycle = cycle[j[u]:]
            cycle.reverse()
            return cycle
        v = u
