最小費用流 (Primal-Dual 法)
(Flow/MinCostFlow.py)

• View this file on GitHub
• Last update: 2022-01-20 17:35:30+09:00

Verified with

• TestCase/AOJ/GRL_6_B.test.py

Code

# from heapq import heappush, heappop
from standard_library.heapq import heappush, heappop


class MinCostFlow:
    def __init__(self, n):
        self.INF = 10 ** 9 + 7
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, fr, to, cap, cost):
        fr_idx = len(self.graph[fr])
        to_idx = len(self.graph[to])
        if fr == to:
            to_idx += 1
        self.graph[fr].append([to, to_idx, cap, cost])
        self.graph[to].append([fr, fr_idx, 0, -cost])

    def min_cost_flow(self, s, t, flow) -> int:
        res = 0
        potential = [0] * self.n
        prv_v = [0] * self.n
        prv_e = [None] * self.n
        while flow > 0:
            # ポテンシャルを用いたダイクストラ法
            dist = [self.INF] * self.n
            dist[s] = 0
            q = [(0, s)]  # q = [(sからのコスト, 現在地)]
            while q:
                cost, fr = heappop(q)
                if dist[fr] < cost:
                    continue
                for edge in self.graph[fr]:
                    to, _, cap, cost = edge
                    p_diff = potential[fr] - potential[to]
                    if cap > 0 and dist[fr] + cost + p_diff < dist[to]:
                        dist[to] = dist[fr] + cost + p_diff
                        prv_v[to] = fr
                        prv_e[to] = edge
                        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 = flow
            v = t
            while v != s:
                d = min(d, prv_e[v][2])
                v = prv_v[v]
            flow -= d
            res += potential[t] * d
            v = t
            while v != s:
                edge = prv_e[v]
                edge[2] -= d
                self.graph[edge[0]][edge[1]][2] += d
                v = prv_v[v]
        return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page