結果

問題 No.1479 Matrix Eraser
ユーザー titia
提出日時 2024-05-07 04:37:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 677 ms / 3,000 ms
コード長 2,759 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 130,432 KB
最終ジャッジ日時 2024-11-29 17:47:20
合計ジャッジ時間 15,725 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from operator import itemgetter

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

LIST=[[] for i in range(500050)]

for i in range(H):
    for j in range(W):
        LIST[A[i][j]].append(i*W+j)

LANS=0   
# dinic法

from collections import defaultdict,deque

for tt in range(1,500020):
    LL=LIST[tt]

    if LL==[]:
        continue
    if len(LL)==1:
        LANS+=1
        continue

    LH=[]
    LW=[]

    for ll in LL:
        LH.append(ll//W)
        LW.append(ll%W)

    LH=sorted(set(LH))
    LW=sorted(set(LW))

    DH={LH[i]:i for i in range(len(LH))}
    DW={LW[i]:i for i in range(len(LW))}
    
    V=len(LH)+len(LW)+2

    start=V-2
    goal=V-1

    EDGE=[defaultdict(int) for i in range(V)]

    for i in range(len(LH)):
        EDGE[start][i]=1

    for i in range(len(LW)):
        EDGE[i+len(LH)][goal]=1

    for ll in LL:
        h=ll//W
        w=ll%W
        EDGE[DH[h]][DW[w]+len(LH)]=1000000

    

    ANS=0
    while True:
        # まずBFSする

        DIS=[-1]*V
        Q=deque([start])
        DIS[start]=0
        EDGE2=[[] for i in range(V)]

        while Q:
            x=Q.popleft()
            for to in EDGE[x]:
                if EDGE[x][to]==0:
                    continue
                
                if DIS[to]==-1:
                    DIS[to]=DIS[x]+1
                    Q.append(to)
                    EDGE2[x].append(to)
                    
                elif DIS[to]==DIS[x]+1:
                    EDGE2[x].append(to)

        if DIS[goal]==-1:
            break

        # BFSしたときのEDGEを使ってDFSする

        MINCOST=[float("inf")]*V
        NOW=start
        ROUTE=[-1]*V
        
        while NOW!=-1: # DFS

            cost=MINCOST[NOW]
            
            if NOW==goal:
                ANS+=cost
                i=goal
                
                while i!=start: # goalからたどり,Routeを使ってEDGEの更新
                    j=ROUTE[i]
                    if EDGE[j][i]==cost:
                        NOW=j
                        EDGE2[j].pop()
                    
                    EDGE[j][i]-=cost # 使ったルートをいけなく更新
                    MINCOST[j]-=cost                
                    EDGE[i][j]+=cost # 逆向きに進めるようにする.
                    i=j
                continue

            if EDGE2[NOW]:
                to=EDGE2[NOW][-1]
                ROUTE[to]=NOW
                MINCOST[to]=min(cost,EDGE[NOW][to])
                NOW=to

            else:
                if NOW==start:
                    break
                EDGE2[ROUTE[NOW]].pop()
                NOW=ROUTE[NOW]
    LANS+=ANS
         

print(LANS)
0