結果

問題 No.1479 Matrix Eraser
ユーザー zkouzkou
提出日時 2021-04-16 21:32:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,037 ms / 3,000 ms
コード長 7,532 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 153,536 KB
最終ジャッジ日時 2024-07-03 00:56:04
合計ジャッジ時間 23,076 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
55,108 KB
testcase_01 AC 43 ms
56,756 KB
testcase_02 AC 45 ms
56,044 KB
testcase_03 AC 45 ms
56,836 KB
testcase_04 AC 46 ms
56,884 KB
testcase_05 AC 45 ms
56,724 KB
testcase_06 AC 45 ms
56,128 KB
testcase_07 AC 345 ms
84,448 KB
testcase_08 AC 434 ms
91,156 KB
testcase_09 AC 569 ms
103,344 KB
testcase_10 AC 885 ms
116,116 KB
testcase_11 AC 631 ms
101,136 KB
testcase_12 AC 338 ms
86,132 KB
testcase_13 AC 385 ms
91,360 KB
testcase_14 AC 357 ms
86,576 KB
testcase_15 AC 205 ms
81,336 KB
testcase_16 AC 377 ms
86,660 KB
testcase_17 AC 986 ms
132,804 KB
testcase_18 AC 1,037 ms
132,896 KB
testcase_19 AC 981 ms
132,512 KB
testcase_20 AC 972 ms
132,644 KB
testcase_21 AC 996 ms
132,612 KB
testcase_22 AC 991 ms
132,896 KB
testcase_23 AC 1,002 ms
132,776 KB
testcase_24 AC 1,007 ms
132,428 KB
testcase_25 AC 1,004 ms
133,012 KB
testcase_26 AC 991 ms
133,012 KB
testcase_27 AC 566 ms
106,148 KB
testcase_28 AC 571 ms
105,760 KB
testcase_29 AC 532 ms
104,956 KB
testcase_30 AC 580 ms
107,016 KB
testcase_31 AC 547 ms
105,136 KB
testcase_32 AC 401 ms
147,284 KB
testcase_33 AC 422 ms
153,536 KB
testcase_34 AC 406 ms
147,160 KB
testcase_35 AC 425 ms
153,160 KB
testcase_36 AC 402 ms
147,176 KB
testcase_37 AC 94 ms
96,028 KB
testcase_38 AC 476 ms
109,156 KB
testcase_39 AC 850 ms
145,180 KB
testcase_40 AC 43 ms
56,756 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

class mf_graph:
    """It solves maximum flow problem.
    """

    def __init__(self, n):
        """It creates a graph of n vertices and 0 edges.

        Constraints
        -----------

        >   0 <= n <= 10 ** 8

        Complexity
        ----------

        >   O(n)
        """
        self.n = n
        self.g = [[] for _ in range(self.n)]
        self.pos = []

    def add_edge(self, from_, to, cap):
        """It adds an edge oriented from the vertex `from_` to the vertex `to` 
        with the capacity `cap` and the flow amount 0. 
        It returns an integer k such that this is the k-th edge that is added.

        Constraints
        -----------

        >   0 <= from_, to < n

        >   0 <= cap

        Complexity
        ----------

        >   O(1) amortized
        """
        # assert 0 <= from_ < self.n
        # assert 0 <= to < self.n
        # assert 0 <= cap
        m = len(self.pos)
        self.pos.append((from_, len(self.g[from_])))
        from_id = len(self.g[from_])
        to_id = len(self.g[to])
        if from_ == to:
            to_id += 1
        self.g[from_].append(self.__class__._edge(to, to_id, cap))
        self.g[to].append(self.__class__._edge(from_, from_id, 0))
        return m

    class edge:
        def __init__(self, from_, to, cap, flow):
            self.from_ = from_
            self.to = to
            self.cap = cap
            self.flow = flow

    def get_edge(self, i):
        """It returns the current internal state of the edges.
        The edges are ordered in the same order as added by `add_edge`.

        Constraints
        -----------

        >   0 <= i < m

        Complexity
        ----------

        >   O(1)
        """
        # assert 0 <= i < len(self.pos)
        _e = self.g[self.pos[i][0]][self.pos[i][1]]
        _re = self.g[_e.to][_e.rev]
        return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

    def edges(self):
        """It returns the current internal state of the edges.
        The edges are ordered in the same order as added by `add_edge`.

        Complexity
        ----------

        >   O(m), where m is the number of added edges.
        """
        result = []
        for i in range(len(self.pos)):
            _e = self.g[self.pos[i][0]][self.pos[i][1]]
            _re = self.g[_e.to][_e.rev]
            result.append(self.__class__.edge(
                self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap))
        return result

    def change_edge(self, i, new_cap, new_flow):
        """It changes the capacity and the flow amount of the i-th edge to `new_cap` and `new_flow`, respectively. 
        It doesn't change the capacity or the flow amount of other edges. 
        See Appendix in the document of AC Library for further details.

        Constraints
        -----------

        >   0 <= i < m

        >   0 <= new_flow <= new_cap

        Complexity
        ----------

        >   O(1)
        """
        # assert 0 <= i < len(self.pos)
        # assert 0 <= new_flow <= new_cap
        _e = self.g[self.pos[i][0]][self.pos[i][1]]
        _re = self.g[_e.to][_e.rev]
        _e.cap = new_cap - new_flow
        _re.cap = new_flow

    def _bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = [s]
        while q:
            nq = []
            for v in q:
                for e in self.g[v]:
                    if e.cap and self.level[e.to] == -1:
                        self.level[e.to] = self.level[v] + 1
                        if e.to == t:
                            return True
                        nq.append(e.to)
            q = nq
        return False

    def _dfs(self, s, t, up):
        st = [t]
        while st:
            v = st[-1]
            if v == s:
                st.pop()
                flow = up
                for w in st:
                    e = self.g[w][self.it[w]]
                    flow = min(flow, self.g[e.to][e.rev].cap)
                for w in st:
                    e = self.g[w][self.it[w]]
                    e.cap += flow
                    self.g[e.to][e.rev].cap -= flow
                return flow
            while self.it[v] < len(self.g[v]):
                e = self.g[v][self.it[v]]
                w = e.to
                cap = self.g[e.to][e.rev].cap
                if cap and self.level[v] > self.level[w]:
                    st.append(w)
                    break
                self.it[v] += 1
            else:
                st.pop()
                self.level[v] = self.n
        return 0

    def flow(self, s, t, flow_limit=float('inf')):
        """It augments the flow from s to t as much as possible. 
        It returns the amount of the flow augmented.
        You may call it multiple times. 
        See Appendix in the document of AC Library for further details.

        Constraints
        -----------

        >   0 <= s, t < n

        >   s != t

        Complexity
        ----------

        >   O(min(n^(2/3)m, m^(3/2))) (if all the capacities are 1) or

        >   O(n^2 m) (general),

        where m is the number of added edges.
        """
        # assert 0 <= s < self.n
        # assert 0 <= t < self.n
        # assert s != t
        flow = 0
        while flow < flow_limit and self._bfs(s, t):
            self.it = [0] * self.n
            while flow < flow_limit:
                f = self._dfs(s, t, flow_limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        """It returns a list of length n, 
        such that the i-th element is `True` if and only if there is a directed path from s to i in the residual network. 
        The returned list corresponds to a s−t minimum cut after calling flow(s, t) exactly once without flow_limit. 
        See Appendix in the document of AC Library for further details.

        Constraints
        -----------

        >   0 <= s < n

        Complexity
        ----------

        >   O(n + m), where m is the number of added edges.
        """
        visited = [False] * self.n
        q = [s]
        while q:
            nq = []
            for p in q:
                visited[p] = True
                for e in self.g[p]:
                    if e.cap and not visited[e.to]:
                        visited[e.to] = True
                        nq.append(e.to)
            q = nq
        return visited

    class _edge:
        def __init__(self, to, rev, cap):
            self.to = to
            self.rev = rev
            self.cap = cap


from collections import defaultdict

H, W = map(int, input().split())
As = [list(map(int, input().split())) for _ in range(H)]

vals = defaultdict(list)
for i in range(H):
    for j in range(W):
        vals[As[i][j]].append((i, j))

answer = 0
for key in sorted(vals.keys(), reverse=True):
    if key == 0:
        break
    indices = vals[key]
    i_set = set()
    j_set = set()
    for i, j in indices:
        i_set.add(i)
        j_set.add(j)
    i_encode = {e: i for i, e in enumerate(i_set)}
    j_encode = {e: j for j, e in enumerate(j_set)}
    h = len(i_encode)
    w = len(j_encode)
    g = mf_graph(h + w + 2)
    s = h + w
    t = s + 1
    for i, j in indices:
        i = i_encode[i]
        j = j_encode[j]
        g.add_edge(i, j + h, 1)
    for i in range(h):
        g.add_edge(s, i, 1)
    for j in range(w):
        g.add_edge(h + j, t, 1)
    answer += g.flow(s, t)
    # print(answer)

print(answer)
0