結果

問題 No.1479 Matrix Eraser
ユーザー None
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

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