Problem:


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

Minimum Cost Flow

  Find the minimum cost to send a certain amount of flow through a flow network.

  The flow network is a directed graph where each edge $e$ has capacity $c(e)$ and cost $d(e)$. Each edge $e$ can send an amount of flow $f(e)$ where $f(e) \leq c(e)$. Find the minimum value of $\sum_{e} (f(e) \times d(e))$ to send an amount of flow $F$ from source $s$ to sink $t$.

Input

A flow network $G(V,E)$ is given in the following format.

$|V|\;|E|\;F$

$u_0\;v_0\;c_0\;d_0$

$u_1\;v_1\;c_1\;d_1$

:

$u_{|E|1}\;v_{|E|-1}\;c_{|E|-1}\;d_{|E|-1}$

  $|V|$, $|E|$, $F$ are the number of vertices, the number of edges, and the amount of flow of the flow network respectively. The vertices in $G$ are named with the numbers $0, 1,..., |V|−1$. The source is $0$ and the sink is $|V|−1$.

$u_i$, $v_i$, $c_i$, $d_i$ represent $i$-th edge of the flow network. A pair of $u_i$ and $v_i$ denotes that there is an edge from $u_i$ to $v_i$, and $c_i$ and $d_i$ are the capacity and the cost of $i$-th edge respectively.

Output

  Print the minimum value in a line. If it is impossible to send the flow from the source $s$ to the sink $t$, print -1.

Constraints

 2 ≤ $|V|$ ≤ 100
	

 1 ≤ $|E|$ ≤ 1000

 0 ≤ $F$ ≤ 1000
		

 0 ≤ $c_i$, $d_i$ ≤ 1000
	

 $u_i$ $\ne$ $v_i$

 If there is an edge from vertex $x$ to vertex $y$, there is no edge from vertex $y$ to vertex $x$.

Sample Input

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1

Sample Output

6



Sample input:
4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1


Sample output:
6

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def trace(source, edge_trace):
    v = source
    for i in edge_trace:
        e = edges[v][i]
        yield e
        v = e[1]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        dist = [-1] * n
        queue = [(0, source, tuple())]
        edge_trace = None
        while queue:
            total_cost, v, edge_memo = heappop(queue)
            dist[v] = total_cost
            if v == sink:
                edge_trace = edge_memo
                break
            for i, (remain, target, cost, _) in enumerate(edges[v]):
                if remain and dist[target] == -1:
                    heappush(queue, (total_cost + cost, target, edge_memo + (i,)))

        if dist[sink] == -1:
            return -1

        aug = min(e[0] for e in trace(source, edge_trace))
        required_flow -= aug
        res += aug * dist[sink]
        for e in trace(source, edge_trace):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


n, m, f = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(m):
    s, t, c, d = map(int, input().split())
    es, et = edges[s], edges[t]
    ls, lt = len(es), len(et)
    es.append([c, t, d, lt])
    et.append([0, s, d, ls])

print(min_cost_flow(0, n - 1, f))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def trace(source, edge_trace):
    v = source
    for i in edge_trace:
        e = edges[v][i]
        yield e
        v = e[1]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        dist = [-1] * n
        queue = [(0, source, tuple())]
        edge_trace = None
        while queue:
            total_cost, v, edge_memo = heappop(queue)
            if dist[v] != -1:
                continue
            dist[v] = total_cost
            if v == sink:
                edge_trace = edge_memo
                break
            for i, (remain, target, cost, _) in enumerate(edges[v]):
                if remain and dist[target] == -1:
                    heappush(queue, (total_cost + cost, target, edge_memo + (i,)))

        if dist[sink] == -1:
            return -1

        aug = min(e[0] for e in trace(source, edge_trace))
        required_flow -= aug
        res += aug * dist[sink]
        for e in trace(source, edge_trace):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


n, m, f = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(m):
    s, t, c, d = map(int, input().split())
    es, et = edges[s], edges[t]
    ls, lt = len(es), len(et)
    es.append([c, t, d, lt])
    et.append([0, s, d, ls])

print(min_cost_flow(0, n - 1, f))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def trace(source, edge_trace):
    v = source
    for i in edge_trace:
        e = edges[v][i]
        yield e
        v = e[1]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        dist = [-1] * n
        queue = [(0, source, tuple())]
        edge_trace = None
        while queue:
            total_cost, v, edge_memo = heappop(queue)
            if dist[v] != -1:
                continue
            dist[v] = total_cost
            if v == sink:
                edge_trace = edge_memo
                break
            for i, (remain, target, cost, _) in enumerate(edges[v]):
                if remain and dist[target] == -1:
                    heappush(queue, (total_cost + cost, target, edge_memo + (i,)))

        if dist[sink] == -1:
            return -1

        aug = min(required_flow, min(e[0] for e in trace(source, edge_trace)))
        required_flow -= aug
        res += aug * dist[sink]
        for e in trace(source, edge_trace):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


n, m, f = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(m):
    s, t, c, d = map(int, input().split())
    es, et = edges[s], edges[t]
    ls, lt = len(es), len(et)
    es.append([c, t, d, lt])
    et.append([0, s, d, ls])

print(min_cost_flow(0, n - 1, f))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def trace(source, edge_trace):
    v = source
    for i in edge_trace:
        e = edges[v][i]
        yield e
        v = e[1]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        visited = set()
        queue = [(0, source, tuple())]
        while queue:
            total_cost, v, edge_memo = heappop(queue)
            if v in visited:
                continue
            elif v == sink:
                dist = total_cost
                edge_trace = edge_memo
                break
            visited.add(v)
            for i, (remain, target, cost, _) in enumerate(edges[v]):
                if remain and target not in visited:
                    heappush(queue, (total_cost + cost, target, edge_memo + (i,)))
        else:
            return -1

        aug = min(required_flow, min(e[0] for e in trace(source, edge_trace)))
        required_flow -= aug
        res += aug * dist
        for e in trace(source, edge_trace):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


n, m, f = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(m):
    s, t, c, d = map(int, input().split())
    es, et = edges[s], edges[t]
    ls, lt = len(es), len(et)
    es.append([c, t, d, lt])
    et.append([0, s, d, ls])

print(min_cost_flow(0, n - 1, f))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def trace(source, edge_trace):
    v = source
    for i in edge_trace:
        e = edges[v][i]
        yield e
        v = e[1]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        visited = set()
        queue = [(0, source, tuple())]
        while queue:
            total_cost, v, edge_memo = heappop(queue)
            if v in visited:
                continue
            elif v == sink:
                dist = total_cost
                edge_trace = edge_memo
                break
            visited.add(v)
            for i, (remain, target, cost, _) in enumerate(edges[v]):
                if remain and target not in visited:
                    heappush(queue, (total_cost + cost, target, edge_memo + (i,)))
        else:
            return -1

        aug = min(required_flow, min(e[0] for e in trace(source, edge_trace)))
        required_flow -= aug
        res += aug * dist
        for e in trace(source, edge_trace):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


n, m, f = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(m):
    s, t, c, d = map(int, input().split())
    es, et = edges[s], edges[t]
    ls, lt = len(es), len(et)
    es.append([c, t, d, lt])
    et.append([0, s, -d, ls])

print(min_cost_flow(0, n - 1, f))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

v_num, e_num, flow = (int(n) for n in input().split(" "))
edges = defaultdict(list)
for _ in range(e_num):
    s1, t1, cap, cost = (int(n) for n in input().split(" "))
    edges[s1].append([t1, cap, cost, len(edges[t1])])
    edges[t1].append([s1, cap, cost, len(edges[s1])])
answer = 0
before_vertice = [float("inf") for n in range(v_num)]
before_edge = [float("inf") for n in range(v_num)]
sink = v_num - 1
while True:
    distance = [float("inf") for n in range(v_num)]
    distance[0] = 0
    updated = 1
    while updated:
        updated = 0
        for v in range(v_num):
            if distance[v] == float("inf"):
                continue
            for i, (target, cap, cost, trace_i) in enumerate(edges[v]):
                if cap > 0 and distance[target] > distance[v] + cost:
                    distance[target] = distance[v] + cost
                    before_vertice[target] = v
                    before_edge[target] = i
                    updated = 1
    if distance[sink] == float("inf"):
        print(-1)
        break
    decreased = flow
    trace_i = sink
    while trace_i != 0:
        decreased = min(decreased, edges[before_vertice[trace_i]][before_edge[trace_i]][1])
        trace_i = before_vertice[trace_i]
    flow -= decreased
    answer += decreased * distance[sink]
    trace_i = sink
    while trace_i != 0:
        this_edge = edges[before_vertice[trace_i]][before_edge[trace_i]]
        this_edge[1] -= decreased
        trace_i = before_vertice[trace_i]
        edges[trace_i][this_edge[3]][1] += decreased
    if flow <= 0:
        print(answer)
        break

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

v_num, e_num, flow = (int(n) for n in input().split(" "))
edges = defaultdict(list)
for _ in range(e_num):
    s1, t1, cap, cost = (int(n) for n in input().split(" "))
    edges[s1].append([t1, cap, cost, len(edges[t1])])
    edges[t1].append([s1, cap, cost, len(edges[s1]) - 1])
answer = 0
before_vertice = [float("inf") for n in range(v_num)]
before_edge = [float("inf") for n in range(v_num)]
sink = v_num - 1
while True:
    distance = [float("inf") for n in range(v_num)]
    distance[0] = 0
    updated = 1
    while updated:
        updated = 0
        for v in range(v_num):
            if distance[v] == float("inf"):
                continue
            for i, (target, cap, cost, trace_i) in enumerate(edges[v]):
                if cap > 0 and distance[target] > distance[v] + cost:
                    distance[target] = distance[v] + cost
                    before_vertice[target] = v
                    before_edge[target] = i
                    updated = 1
    if distance[sink] == float("inf"):
        print(-1)
        break
    decreased = flow
    trace_i = sink
    while trace_i != 0:
        decreased = min(decreased, edges[before_vertice[trace_i]][before_edge[trace_i]][1])
        trace_i = before_vertice[trace_i]
    flow -= decreased
    trace_i = sink
    while trace_i != 0:
        this_edge = edges[before_vertice[trace_i]][before_edge[trace_i]]
        this_edge[1] -= decreased
        answer += this_edge[2] * decreased
        edges[trace_i][this_edge[3]][1] += decreased
        trace_i = before_vertice[trace_i]
    if flow <= 0:
        print(answer)
        break

Submission status: Accepted

Solution code:
INF = float('inf')


def trace_back(sink, predecessors):
    p = predecessors[sink]
    while p is not None:
        v, i = p
        yield edges[v][i]
        p = predecessors[v]


def min_cost_flow(source, sink, required_flow):
    res = 0
    while required_flow:
        dist = [INF] * n
        dist[source] = 0
        predecessors = [None] * n

        while True:
            updated = False
            for v in range(n):
                if dist[v] == INF:
                    continue
                for i, (remain, target, cost, _) in enumerate(edges[v]):
                    new_dist = dist[v] + cost
                    if remain and dist[target] > new_dist:
                        dist[target] = new_dist
                        predecessors[target] = (v, i)
                        updated = True
            if not updated:
                break

        if dist[sink] == INF:
            return -1

        aug = min(required_flow, min(e[0] for e in trace_back(sink, predecessors)))
        required_flow -= aug
        res += aug * dist[sink]
        for e in trace_back(sink, predecessors):
            remain, target, cost, idx = e
            e[0] -= aug
            edges[target][idx][0] += aug
    return res


n, m, f = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(m):
    s, t, c, d = map(int, input().split())
    es, et = edges[s], edges[t]
    ls, lt = len(es), len(et)
    es.append([c, t, d, lt])
    et.append([0, s, -d, ls])

print(min_cost_flow(0, n - 1, f))

Submission status: Accepted

Solution code:
import heapq


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

    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    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 run(self, source, sink, f, INF=10**5):
        res = 0
        h, prevv, preve = [0] * self.V, [0] * self.V, [0] * self.V
        while (f > 0):
            pque = []
            dist = [INF] * self.V
            dist[source] = 0
            heapq.heappush(pque, (0, source))
            while pque:
                cost, v = heapq.heappop(pque)
                cost = -cost
                if dist[v] < cost:
                    continue
                for i, e in enumerate(self.E[v]):
                    if e.cap > 0 and dist[v] - h[e.to] < dist[e.to] - e.cost - h[v]:
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]
                        prevv[e.to], preve[e.to] = v, i
                        heapq.heappush(pque, (-dist[e.to], e.to))
            if dist[sink] == INF:
                return -1
            for v in range(self.V):
                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

V, E, F = map(int, input().split())
mcf = MinCostFlow(V)
for _ in range(E):
    u, v, c, d = map(int, input().split())
    mcf.add_edge(u, v, c, d)
print(mcf.run(0, V - 1, F))

Submission status: Accepted

Solution code:
class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.G = [[] for i in range(n)]

    def addEdge(self, f, t, cap, cost):
        # [to, cap, cost, rev]
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f])-1])

    def minCostFlow(self, s, t, f):
        n = self.n
        G = self.G
        prevv = [0]*n; preve = [0]*n
        INF = 10**9+7

        res = 0
        while f:
            dist = [INF]*n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v; preve[to] = i
                            update = 1
            if dist[t] == INF:
                return -1

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

n, m, f = map(int, input().split())
graph = MinCostFlow(n)
for i in range(m):
    u, v, c, d = map(int, input().split())
    graph.addEdge(u, v, c, d)
print(graph.minCostFlow(0, n-1, f))

Submission status: Accepted

Solution code:
from collections import defaultdict

v_num, e_num, flow = (int(n) for n in input().split(" "))
edges = defaultdict(list)
for _ in range(e_num):
    s1, t1, cap, cost = (int(n) for n in input().split(" "))
    edges[s1].append([t1, cap, cost, len(edges[t1])])
    edges[t1].append([s1, 0, -cost, len(edges[s1]) - 1])
answer = 0
before_vertice = [float("inf") for n in range(v_num)]
before_edge = [float("inf") for n in range(v_num)]
sink = v_num - 1
while True:
    distance = [float("inf") for n in range(v_num)]
    distance[0] = 0
    updated = 1
    while updated:
        updated = 0
        for v in range(v_num):
            if distance[v] == float("inf"):
                continue
            for i, (target, cap, cost, trace_i) in enumerate(edges[v]):
                if cap > 0 and distance[target] > distance[v] + cost:
                    distance[target] = distance[v] + cost
                    before_vertice[target] = v
                    before_edge[target] = i
                    updated = 1
    if distance[sink] == float("inf"):
        print(-1)
        break
    decreased = flow
    trace_i = sink
    while trace_i != 0:
        decreased = min(decreased, edges[before_vertice[trace_i]][before_edge[trace_i]][1])
        trace_i = before_vertice[trace_i]
    flow -= decreased
    trace_i = sink
    while trace_i != 0:
        this_edge = edges[before_vertice[trace_i]][before_edge[trace_i]]
        this_edge[1] -= decreased
        answer += this_edge[2] * decreased
        edges[trace_i][this_edge[3]][1] += decreased
        trace_i = before_vertice[trace_i]
    if flow <= 0:
        print(answer)
        break

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

class Edge():
    def __init__(self,t,f,r,ca,co):
        self.to = t
        self.fron = f
        self.rev = r
        self.cap = ca
        self.cost = co

class MinCostFlow():
    size = 0
    graph = []

    def __init__(self, s):
        self.size = s
        self.graph = [[] for _ in range(s)]

    def add_edge(self, f, t, ca, co):
        self.graph[f].append(Edge(t, f, len(self.graph[t]), ca, co))
        self.graph[t].append(Edge(f, t, len(self.graph[f])-1, 0, -co))

    def min_path(self, s, t):
        dist = [inf] * self.size
        route = [None] * self.size
        que = collections.deque()
        inq = [False] * self.size
        dist[s] = 0
        que.append(s)
        inq[s] = True
        while que:
            u = que.popleft()
            inq[u] = False
            for e in self.graph[u]:
                if e.cap == 0:
                    continue
                v = e.to
                if dist[v] > dist[u] + e.cost:
                    dist[v] = dist[u] + e.cost
                    route[v] = e
                    if not inq[v]:
                        que.append(v)
                        inq[v] = True

        if dist[t] == inf:
            return inf, 0

        flow = inf
        v = t
        while v != s:
            e = route[v]
            if flow > e.cap:
                flow = e.cap
            v = e.fron

        c = 0
        v = t
        while v != s:
            e = route[v]
            e.cap -= flow
            self.graph[e.to][e.rev].cap += flow
            c += e.cost * flow
            v = e.fron

        return dist[t], flow

    def calc_min_cost_flow(self, s, t, flow):
        total_cost = 0
        while flow > 0:
            c,f = self.min_path(s, t)
            if f == 0:
                return inf
            f = min(flow, f)
            total_cost += c * f
            flow -= f

        return total_cost


def main():
    n,m,f = LI()
    uvcd = [LI() for _ in range(m)]

    mf = MinCostFlow(n)
    for u,v,c,d in uvcd:
        mf.add_edge(u,v,c,d)

    r = mf.calc_min_cost_flow(0, n-1, f)
    if r == inf:
        return -1

    return r

# start = time.time()
print(main())
# pe(time.time() - start)

Submission status: Accepted

Solution code:
import heapq

class edge:
    def __init__(self, to, cap, cost, rev):
        self.to: int = to
        self.cap: int = cap
        self.cost: int = cost
        self.rev: int = rev


class min_cost_flow:
    def __init__(self, N):
        self.N: int = N
        self.INF: int = 1000000000000000000
        self.G = [[] for i in range(N)]
        
    def add_edge(self, fro, to, cap, cost):
        self.G[fro].append(edge(to, cap, int(cost), int(len(self.G[to]))))
        self.G[to].append(edge(fro, 0, -int(cost), int(len(self.G[fro]) - 1)))
        
    def solve(self, s, t, f):
        N = self.N
        prevv = [0 for i in range(N)]
        preve = [0 for i in range(N)]
        
        ret = 0
        while 0 < f:
            dist = [self.INF for i in range(N)]
            dist[s] = 0
            hq = [(0, s)]
            heapq.heapify(hq)
            while hq:
                d, v = heapq.heappop(hq)
                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    if 0 < e.cap and dist[v] + e.cost < dist[e.to]:
                        dist[e.to] = dist[v] + e.cost
                        prevv[e.to] = v
                        preve[e.to] = i
                        heapq.heappush(hq, (dist[e.to], e.to))

            # 流せない
            if dist[t] == self.INF:
                return self.INF

            d = f
            v = t
            while v != s:
                d = min(d, self.G[prevv[v]][preve[v]].cap)
                v = prevv[v]

            f -= d
            ret += d * dist[t]
            v = t
            while v != s:
                e = self.G[prevv[v]][preve[v]]
                e.cap -= d
                self.G[v][e.rev].cap += d
                v = prevv[v]
    
        return ret

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_B
v, e, f = map(int, input().split())
mcf = min_cost_flow(v)
for i in range(e):
    ui, vi, ci, di = map(int, input().split())
    mcf.add_edge(ui, vi, ci, di)
    
ans = mcf.solve(0, v-1, f)
if ans == mcf.INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import heapq


class PrimalDual:
    def __init__(self, n: int):
        """頂点数をnとする。"""
        self.INF = 10 ** 9 + 7
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, _from: int, to: int, capacity: int, cost: int):
        """辺を追加
        1. _fromからtoへ向かう容量capacity、単位コストcostの辺をグラフに追加する。
        2. toから_fromへ向かう容量0、単位コスト-costの辺をグラフに追加する。
        """
        forward = [to, capacity, cost, None]
        forward[3] = backward = [_from, 0, -cost, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)

    def min_cost_flow(self, s: int, t: int, f: int) -> int:
        """s-tパス上に流量fを流すときの最小費用流を求める。
        計算量: O(|F||E|log|V|)
        """
        res = 0
        potential = [0] * self.n
        prv_v = [0] * self.n
        prv_e = [None] * self.n
        while f > 0:
            # ポテンシャルを用いたダイクストラ法
            dist = [self.INF] * self.n
            dist[s] = 0
            q = [(0, s)]  # q = [(sからのコスト, 現在地)]
            while q:
                cost, _from = heapq.heappop(q)
                if dist[_from] < cost:
                    continue
                for edge in self.graph[_from]:
                    to, capacity, cost, _ = edge
                    p_diff = potential[_from] - potential[to]
                    if capacity > 0 and dist[_from] + cost + p_diff < dist[to]:
                        dist[to] = dist[_from] + cost + p_diff
                        prv_v[to] = _from
                        prv_e[to] = edge
                        heapq.heappush(q, (dist[to], to))

            if dist[t] == self.INF:
                return -1
            for i in range(self.n):
                if dist[i] != self.INF:
                    potential[i] += dist[i]
            d = f
            v = t
            while v != s:
                d = min(d, prv_e[v][1])
                v = prv_v[v]
            f -= d
            res += potential[t] * d
            v = t
            while v != s:
                edge = prv_e[v]
                edge[1] -= d
                edge[3][1] += d
                v = prv_v[v]
        return res


n, m, f = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]


pd = PrimalDual(n)
for edge in edges:
    pd.add_edge(*edge)
    
ans = pd.min_cost_flow(0, n - 1, f)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

class MinimumCostFlow:
    inf = 1000000000
    def __init__(self, n):
        self.n = n
        self.edges = [[] for i in range(n)]
    def add_edge(self, f, t, cap, cost):
        self.edges[f].append([t, cap, cost, len(self.edges[t]), False])
        self.edges[t].append([f, 0, -cost, len(self.edges[f]) - 1, True]) # reverse edge
    def flow(self, s, t, flow):
        n = self.n
        g = self.edges
        inf = MinimumCostFlow.inf

        prevv = [0 for i in range(n)]
        preve = [0 for i in range(n)]
        h = [0 for i in range(n)]
        dist = [inf for i in range(n)]

        res = 0

        while flow != 0:
            dist = [inf for i in range(n)]
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                r0 = dist[v] + h[v]
                for i, e in enumerate(g[v]):
                    w, cap, cost, _, _ = e
                    if cap > 0 and r0 + cost - h[w] < dist[w]:
                        r = r0 + cost - h[w]
                        dist[w] = r
                        prevv[w] = v
                        preve[w] = i
                        heappush(que, (r, w))

            if dist[t] == inf:
                return -1
            
            for i in range(n):
                h[i] += dist[i]

            d = flow
            v = t
            while v != s:
                d = min(d, g[prevv[v]][preve[v]][1])
                v = prevv[v]
            flow -= d
            res += d * h[t]
            v = t
            while v != s:
                e = g[prevv[v]][preve[v]]
                e[1] -= d
                g[v][e[3]][1] += d
                v = prevv[v]
        return res

import sys
readline = sys.stdin.readline
write = sys.stdout.write
N, M, F = map(int, readline().split())

mcf = MinimumCostFlow(N)
for i in range(M):
    u, v, c, d = map(int, readline().split())
    mcf.add_edge(u, v, c, d)
write("%d\n" % mcf.flow(0, N-1, F))

Submission status: Accepted

Solution code:
#最小費用流問題
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,m,f = map(int,readline().split())
"""
n頂点m辺の重み付き有向グラフに流量fを流したい。
コストの最小値を出力せよ。
但しsourse = 0,sink = n-1とし、
そもそも流量f流せるだけcapacityがない場合は-1を出力せよ。
"""
# 最小費用流(minimum cost flow)
class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.G = [[] for i in range(n)]

    def addEdge(self, f, t, cap, cost): #costは1capに対して1costで定義される
        # [to, cap, cost, rev]↓revは勝手に逆辺張ってくれるので考えなくて良い。
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f])-1])

    def minCostFlow(self, s, t, f): #sからtまで、流量fを流し切る
        n = self.n
        G = self.G
        prevv = [0]*n; preve = [0]*n
        INF = 10**18

        res = 0 #コスト合計
        while f:
            dist = [INF]*n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v; preve[to] = i
                            update = 1
            if dist[t] == INF: #そもそもcapacity的に流量fを流せない場合
                return -1

            d = f; v = t
            while v != s:
                d = min(d, G[prevv[v]][preve[v]][1])
                v = prevv[v]
            f -= d
            res += d * dist[t] #distには、一本の道全体としての単位コストが入っている。
            #dだけ流せるので、d*その道全体のコストを,コスト合計のresに入れる。
            v = t
            while v != s:
                e = G[prevv[v]][preve[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prevv[v]
        return res

MCF = MinCostFlow(n)
for i in range(m):
    u,v,cap,cost = map(int,readline().split())
    MCF.addEdge(u,v,cap,cost)

print(MCF.minCostFlow(0,n-1,f))