結果

問題 No.1479 Matrix Eraser
コンテスト
ユーザー 小野寺健
提出日時 2021-04-28 18:20:30
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 3,981 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 159 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 36,872 KB
最終ジャッジ日時 2024-07-07 16:01:14
合計ジャッジ時間 6,709 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 28 08:59:11 2021

No1479_2.py

@author: onodera
"""

MAX_V = 500*2+2

class Edge:
    def __init__(self, r, f, t, c):
        self.rev = r
        self.fr = f
        self.to = t
        self.cap = self.icap = c
    def __str__(self):
        if self.cap > 0:
            return str(self.fr) + "->" + str(self.to) + '(' + str(self.cap) + ')'
        else:
            return ""
        
class Graph:
    def __init__(self, n=0):
        self.init(n)
    def init(self, n=0):
        self.V = n
        self.l = [[] for _ in range(MAX_V)]
    def resize(self, n=0):
        self.V = n
    def reset(self):
        for i in range(self.V):
            for j in range(len(self.l[i])):
                self.l[i][j].cap = self.l[i][j].icap
    def get(self, i):
        return self.l[i]
    def redge(self, e):
        if e.fr != e.to:
            return self.l[e.to][e.rev]
        else:
            return self.l[e.to][e.rev+1]
    def addedge(self, fr, to, cap):
        self.l[fr].append(Edge(len(self.l[to]), fr, to, cap))
        self.l[to].append(Edge(len(self.l[fr]) - 1, to, fr, 0))
        
    def __str__(self):
        s = ''
        for l in self.l:
            for e in l:
                s += str(e) + '\n'
        return s

level = [0] * MAX_V
it = [0] * MAX_V

def dibfs(G, s):
    global it, lecel
    for i in range(MAX_V):
        level[i] = -1
    level[s] = 0
    que = [s]
    while len(que) > 0:
        v = que.pop(0)
        for i in range(len(G.get(v))):
            e = G.get(v)[i]
            if level[e.to] < 0 and e.cap > 0:
                level[e.to] = level[v] + 1
                que.append(e.to)
                
def didfs(G, v, t, f):
    global it, lecel
    if v == t:
        return f
    for i in range(it[v], len(G.get(v))):
        e = G.get(v)[i]
        re = G.redge(e)
        if level[v] < level[e.to] and e.cap > 0:
            d = didfs(G, e.to, t, min(f, e.cap))
            if d > 0:
                e.cap -= d
                re.cap += d
                return d
    return 0

def Dinic(G, s, t):
    global it, level
    res = 0
    while True:
        dibfs(G, s)
        if level[t] < 0:
            return res
        it = [0] * MAX_V
        flow = didfs(G, s, t, float('inf'))
        while flow > 0:
            res += flow
            flow = didfs(G, s, t, float('inf'))

def matches(h, w, edges):
    G = Graph(h + w + 2)
    S_node = h + w
    T_node = h + w + 1
    for v in range(h):
        for u in edges[v]:
            G.addedge(v, u + h, 1)
        G.addedge(S_node, v, 1)
    for u in range(w):
        G.addedge(u + h, T_node, 1)
        
    res = Dinic(G, S_node, T_node)
    matched = [-1] * w
    for i in range(h):
        for e in G.get(i):
            if e.icap == 1 and e.cap == 0:
                matched[e.to - h] = i
    return matched
    
def mpc(xn, yn):
    global edges
    matched = matches(xn, yn, edges)

    left = xn
    right = 0

    ledges = []
    redges = matched
    
    for v in range(xn):
        if v not in matched:
            left -= 1
            ledges.append(v)

    for v in ledges:
        for u in edges[v]:
            right += 1
            if redges[u] >= 0:
                left -= 1

    return left + right


if __name__ == '__main__':
    H, W = map(int, input().split())

    S = dict()

    for i in range(H):
        for j, a in enumerate(list(map(int, input().split()))):
            if a > 0:
                if a not in S:
                    S[a] = [set(), set()]
                S[a].append((i, j))
                S[a][0].add(i)
                S[a][1].add(j)
                    
    
    cnt = 0
    for a, pairs in S.items():
        hl = list(pairs[0])
        wl = list(pairs[1]) 
        h = len(hl)
        w = len(wl)
        edges = [set() for _ in range(h)]
        for i, j in pairs[2:]:
            edges[hl.index(i)].add(wl.index(j))
        n = mpc(h, w)
        cnt += n
    
    print(cnt)
0