#882851 (PyPy3) No.957 植林

提出ソース

結果

問題	No.957 植林
ユーザー	vwxyz
提出日時	2023-06-19 14:38:22
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	5,802 bytes
コンパイル時間	168 ms
コンパイル使用メモリ	82,304 KB
実行使用メモリ	112,512 KB
最終ジャッジ日時	2024-06-27 02:59:17
合計ジャッジ時間	10,597 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	160 ms 94,592 KB
testcase_01	AC	160 ms 89,088 KB
testcase_02	AC	157 ms 89,344 KB
testcase_03	AC	371 ms 109,440 KB
testcase_04	AC	344 ms 107,480 KB
testcase_05	AC	358 ms 110,416 KB
testcase_06	AC	375 ms 111,232 KB
testcase_07	AC	357 ms 108,292 KB
testcase_08	AC	293 ms 109,568 KB
testcase_09	AC	295 ms 109,800 KB
testcase_10	AC	305 ms 110,464 KB
testcase_11	AC	300 ms 109,696 KB
testcase_12	AC	293 ms 109,696 KB
testcase_13	AC	271 ms 107,068 KB
testcase_14	AC	292 ms 112,512 KB
testcase_15	AC	286 ms 109,696 KB
testcase_16	AC	275 ms 107,428 KB
testcase_17	AC	287 ms 107,800 KB
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write
from typing import NamedTuple, Optional, List, cast

class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = cast(MFGraph._Edge, e.rev)
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        assert e.rev is not None
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = cast(int, sum(e.cap for e in self._g[s]))

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack: List[MFGraph._Edge] = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        assert e.rev is not None
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = cast(MFGraph._Edge, e.rev)
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited

H,W=map(int,readline().split())
G=[list(map(int,readline().split())) for h in range(H)]
R=list(map(int,readline().split()))
C=list(map(int,readline().split()))
MFG=MFGraph(H+W+2)
s=0
t=H+W+1
ans=0
for h in range(H):
    cost=sum(G[h][w] for w in range(W))-R[h]
    if cost>=0:
        MFG.add_edge(s,h+1,cost)
    else:
        MFG.add_edge(h+1,t,-cost)
        ans+=-cost
for w in range(W):
    cost=-C[w]
    if cost>=0:
        MFG.add_edge(s,w+H+1,cost)
    else:
        MFG.add_edge(w+H+1,t,-cost)
        ans+=-cost
for h in range(H):
    for w in range(W):
        MFG.add_edge(h+1,w+H+1,G[h][w])
flow=MFG.flow(s,t)
ans-=flow
print(ans)

yukicoder

結果

テストケース

ソースコード