#853315 (Python3) No.421 しろくろチョコレート

• 問題: No.421 しろくろチョコレート
• ユーザー: titia
• 提出日時: 2023-03-27 00:23:47
• 言語: Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1)
• 結果: AC
• 実行時間: 207 ms / 2,000 ms
• コード長: 2,340 bytes
• コンパイル時間: 131 ms
• コンパイル使用メモリ: 13,056 KB
• 実行使用メモリ: 12,416 KB
• 最終ジャッジ日時: 2024-09-19 10:04:13
• 合計ジャッジ時間: 5,877 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
other	AC * 65

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import sys
input = sys.stdin.readline
# dinic法
from collections import defaultdict,deque
N,M=map(int,input().split())
MAP=[input().strip() for i in range(N)]
V=N*M+2
EDGE=[defaultdict(int) for i in range(N*M+2)]
for i in range(N):
    for j in range(M):
        if MAP[i][j]=="w":
            for z,w in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if 0<=z<N and 0<=w<M and MAP[z][w]=="b":
                    EDGE[i*M+j][z*M+w]=1
start=N*M
goal=N*M+1
for i in range(N):
    for j in range(M):
        if MAP[i][j]=="w":
            EDGE[start][i*M+j]=1
        else:
            EDGE[i*M+j][goal]=1
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]
            
ws=0
bs=0
for i in range(N):
    for j in range(M):
        if MAP[i][j]=="w":
            ws+=1
        elif MAP[i][j]=="b":
            bs+=1
ws-=ANS
bs-=ANS
k=min(ws,bs)
print(ANS*100+k*10+(ws+bs-k*2))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX