結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
54,272 KB
testcase_01 AC 47 ms
54,528 KB
testcase_02 AC 48 ms
54,528 KB
testcase_03 AC 48 ms
54,272 KB
testcase_04 AC 49 ms
54,656 KB
testcase_05 AC 48 ms
54,272 KB
testcase_06 AC 48 ms
54,912 KB
testcase_07 AC 149 ms
83,420 KB
testcase_08 AC 174 ms
88,064 KB
testcase_09 AC 252 ms
98,716 KB
testcase_10 AC 375 ms
109,852 KB
testcase_11 AC 270 ms
101,628 KB
testcase_12 AC 158 ms
85,120 KB
testcase_13 AC 174 ms
87,936 KB
testcase_14 AC 159 ms
85,248 KB
testcase_15 AC 109 ms
78,336 KB
testcase_16 AC 167 ms
86,528 KB
testcase_17 AC 421 ms
118,336 KB
testcase_18 AC 439 ms
118,336 KB
testcase_19 AC 430 ms
118,448 KB
testcase_20 AC 427 ms
118,592 KB
testcase_21 AC 427 ms
118,592 KB
testcase_22 AC 422 ms
118,432 KB
testcase_23 AC 410 ms
118,452 KB
testcase_24 AC 411 ms
118,580 KB
testcase_25 AC 421 ms
118,328 KB
testcase_26 AC 416 ms
118,608 KB
testcase_27 AC 358 ms
89,384 KB
testcase_28 AC 351 ms
89,780 KB
testcase_29 AC 353 ms
89,228 KB
testcase_30 AC 352 ms
89,820 KB
testcase_31 AC 351 ms
89,640 KB
testcase_32 AC 159 ms
94,720 KB
testcase_33 AC 159 ms
94,976 KB
testcase_34 AC 163 ms
94,976 KB
testcase_35 AC 158 ms
94,976 KB
testcase_36 AC 167 ms
94,976 KB
testcase_37 AC 99 ms
91,400 KB
testcase_38 AC 213 ms
88,448 KB
testcase_39 AC 353 ms
123,168 KB
testcase_40 AC 47 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