結果

問題 No.1479 Matrix Eraser
ユーザー NoneNone
提出日時 2021-05-28 17:34:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 439 ms / 3,000 ms
コード長 3,658 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 123,668 KB
最終ジャッジ日時 2024-04-24 21:03:12
合計ジャッジ時間 13,280 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
54,016 KB
testcase_01 AC 48 ms
54,656 KB
testcase_02 AC 47 ms
54,272 KB
testcase_03 AC 47 ms
54,656 KB
testcase_04 AC 50 ms
54,784 KB
testcase_05 AC 47 ms
54,656 KB
testcase_06 AC 49 ms
54,400 KB
testcase_07 AC 153 ms
83,548 KB
testcase_08 AC 178 ms
88,192 KB
testcase_09 AC 255 ms
98,592 KB
testcase_10 AC 381 ms
110,364 KB
testcase_11 AC 276 ms
101,760 KB
testcase_12 AC 164 ms
85,504 KB
testcase_13 AC 174 ms
87,936 KB
testcase_14 AC 158 ms
85,504 KB
testcase_15 AC 112 ms
78,208 KB
testcase_16 AC 172 ms
86,912 KB
testcase_17 AC 423 ms
118,464 KB
testcase_18 AC 436 ms
118,336 KB
testcase_19 AC 435 ms
118,592 KB
testcase_20 AC 432 ms
118,716 KB
testcase_21 AC 435 ms
118,472 KB
testcase_22 AC 430 ms
118,712 KB
testcase_23 AC 427 ms
118,356 KB
testcase_24 AC 425 ms
118,460 KB
testcase_25 AC 439 ms
118,456 KB
testcase_26 AC 430 ms
118,480 KB
testcase_27 AC 372 ms
89,644 KB
testcase_28 AC 359 ms
89,676 KB
testcase_29 AC 360 ms
89,104 KB
testcase_30 AC 358 ms
89,560 KB
testcase_31 AC 356 ms
89,380 KB
testcase_32 AC 158 ms
94,848 KB
testcase_33 AC 160 ms
95,488 KB
testcase_34 AC 167 ms
95,104 KB
testcase_35 AC 159 ms
94,848 KB
testcase_36 AC 170 ms
95,232 KB
testcase_37 AC 104 ms
91,528 KB
testcase_38 AC 222 ms
88,448 KB
testcase_39 AC 358 ms
123,668 KB
testcase_40 AC 48 ms
54,272 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BipartiteMatching:
    def __init__(self):
        self.len_Y = 0
        self.edges = [[]]

    def add_edge(self, x, y):
        """
        :param x: 頂点集合 X の要素
        :param y: 頂点集合 Y の要素
        """
        while x>=len(self.edges):
            self.edges.append([])
        self.len_Y=max(self.len_Y,y+1)
        self.edges[x].append(y)


    def dfs(self,start):
        """
        :param x: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す(外部からの呼び出し時)
        :return: 増大路が見つかればTrue
        """
        parents_y=dict()
        parents_x=dict()
        x=start
        next_set=[x]
        while next_set:
            x=next_set.pop()
            for y in self.edges[x]:
                if y in parents_y:
                    continue
                if self.matched[y]!=-1:
                    next_x=self.matched[y]
                    next_set.append(next_x)
                    parents_y[y]=x
                    parents_x[next_x]=y
                else:
                    while x!=start:
                        self.matched[y]=x
                        y=parents_x[x]
                        x=parents_y[y]
                    self.matched[y]=x
                    return 1
        return 0

    def solve(self):
        """ 最大マッチング数を返す """
        self.matched = [-1] * self.len_Y  # matched[y]=x: 最大マッチングを考えた時の y とペアの x
        self.len_X=len(self.edges)
        self.visited = set()
        res = 0
        for x in range(self.len_X):
            self.visited = set()
            res += self.dfs(x)
        return res

class MinimumVertexCover:

    def __init__(self):
        self.BM=BipartiteMatching()

    def add_edge(self, x, y):
        self.BM.add_edge(x,y)


    def solve(self):
        BM=self.BM
        BM.solve()
        len_X,len_Y=BM.len_X,BM.len_Y
        edges=BM.edges
        matched=BM.matched
        Xc,Y=[1]*len_X,[0]*len_Y
        for x in range(len_X):
            tmp_X=[x]
            tmp_Y=[]
            for y in edges[x]:
                if matched[y]==x:
                    break
                if matched[y]!=-1:
                    tmp_X.append(matched[y])
                    tmp_Y.append(y)
            else:
                for x in tmp_X:
                    Xc[x]=0
                for y in tmp_Y:
                    Y[y]=1
        res_X,res_Y=[],[]
        for x in range(len_X):
            if Xc[x]==1:
                res_X.append(x)
        for y in range(len_Y):
            if Y[y]==1:
                res_Y.append(y)
        res_X.sort()
        res_Y.sort()
        return res_X,res_Y

#################################################################################################

def example():
    global input
    example = iter(
        """
6 6 8
1 1
2 2
2 4
2 5
3 6
4 3
5 3
6 6
        """
            .strip().split("\n"))
    input = lambda: next(example)



#################################################################################################
import sys
input = sys.stdin.readline
from collections import defaultdict

H,W=map(int, input().split())
d=defaultdict(list)

for h in range(H):
    for w,a in enumerate(map(int, input().split())):
        d[a].append((h,w))

res=0

for a,edges in d.items():
    if a==0:
        continue
    MVC=MinimumVertexCover()
    dh,dw=dict(),dict()
    for h,w in edges:
        if h not in dh:
            dh[h]=len(dh)
        if w not in dw:
            dw[w]=len(dw)
        MVC.add_edge(dh[h],dw[w])
    X,Y=MVC.solve()
    res+=len(X)+len(Y)
print(res)
0