結果

問題 No.421 しろくろチョコレート
ユーザー roaris
提出日時 2019-11-01 14:07:55
言語 PyPy3
(7.0.0)
結果
AC  
実行時間 404 ms
コード長 1,401 Byte
コンパイル時間 1,821 ms
使用メモリ 74,680 KB
最終ジャッジ日時 2019-11-01 14:08:13

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 130 ms
68,460 KB
99_system_test2.txt AC 209 ms
70,660 KB
99_system_test3.txt AC 166 ms
70,016 KB
99_system_test4.txt AC 153 ms
69,312 KB
99_system_test5.txt AC 162 ms
70,112 KB
99_system_test6.txt AC 164 ms
70,392 KB
99_system_test7.txt AC 148 ms
68,580 KB
99_system_test8.txt AC 181 ms
70,568 KB
99_system_test9.txt AC 157 ms
69,768 KB
99_system_test10.txt AC 164 ms
71,964 KB
99_system_test11.txt AC 155 ms
69,212 KB
case_01.txt AC 149 ms
68,760 KB
case_02.txt AC 151 ms
68,948 KB
case_03.txt AC 158 ms
68,816 KB
case_04.txt AC 170 ms
69,300 KB
case_06.txt AC 264 ms
71,928 KB
case_08.txt AC 295 ms
73,272 KB
case_09.txt AC 307 ms
73,364 KB
case_11.txt AC 125 ms
68,456 KB
case_13.txt AC 281 ms
71,420 KB
case_15.txt AC 264 ms
70,988 KB
case_16.txt AC 214 ms
71,824 KB
case_17.txt AC 148 ms
68,456 KB
case_18.txt AC 148 ms
68,460 KB
case_19.txt AC 177 ms
69,472 KB
case_20.txt AC 186 ms
69,272 KB
case_21.txt AC 148 ms
69,496 KB
gunegune_1.txt AC 208 ms
70,776 KB
gunegune_2.txt AC 235 ms
72,108 KB
gunegune_3.txt AC 233 ms
70,856 KB
max.txt AC 276 ms
72,084 KB
pyramid_1.txt AC 234 ms
73,104 KB
pyramid_2.txt AC 224 ms
72,908 KB
sukasuka_1.txt AC 156 ms
69,160 KB
sukasuka_2.txt AC 160 ms
69,376 KB
system_test1.txt AC 196 ms
70,568 KB
system_test2.txt AC 323 ms
73,568 KB
system_test3.txt AC 334 ms
72,612 KB
system_test4.txt AC 192 ms
71,568 KB
system_test5.txt AC 203 ms
72,564 KB
system_test6.txt AC 174 ms
71,940 KB
system_test7.txt AC 166 ms
70,256 KB
system_test8.txt AC 185 ms
70,572 KB
system_test9.txt AC 250 ms
72,172 KB
system_test10.txt AC 164 ms
70,768 KB
system_test11.txt AC 178 ms
70,076 KB
system_test12.txt AC 240 ms
70,600 KB
system_test13.txt AC 246 ms
72,184 KB
system_test14.txt AC 196 ms
70,300 KB
system_test15.txt AC 216 ms
69,952 KB
system_test16.txt AC 270 ms
72,000 KB
system_test17.txt AC 222 ms
72,864 KB
system_test18.txt AC 176 ms
69,232 KB
system_test19.txt AC 188 ms
69,992 KB
system_test20.txt AC 190 ms
70,364 KB
system_test21.txt AC 205 ms
69,152 KB
system_test22.txt AC 190 ms
69,852 KB
system_test23.txt AC 250 ms
71,360 KB
system_test24.txt AC 199 ms
70,668 KB
takusan_1.txt AC 404 ms
74,680 KB
takusan_2.txt AC 310 ms
72,308 KB
tate.txt AC 152 ms
68,456 KB
yoko.txt AC 140 ms
68,936 KB
zero.txt AC 131 ms
68,544 KB
テストケース一括ダウンロード

ソースコード

diff #
import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict

def dfs(v, t, f, used):
    if v == t:
        return f
    
    used[v] = True
    
    for nn, cap in edges[v].items():
        if not used[nn] and cap > 0:
            d = dfs(nn, t, min(f, cap), used)
            
            if d > 0:
                edges[v][nn] -= d
                edges[nn][v] += d
                
                return d
    
    return 0
    
def max_flow(s, t):
    flow = 0
    
    while True:
        used = [False] * (N*M+2)
        f = dfs(s, t, 10**18, used)
        
        if f == 0:
            return flow
            
        flow += f

N, M = map(int, input().split())
S = [input() for _ in range(N)]
edges = defaultdict(dict)
wc, bc = 0, 0

for i in range(N):
    for j in range(M):
        if S[i][j] == 'w':
            wc += 1
            edges[0][M*i+j+1] = 1
            edges[M*i+j+1][0] = 0
            
            for ni, nj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0<=ni<N and 0<=nj<M and S[ni][nj] != '.':
                    edges[M*i+j+1][M*ni+nj+1] = 1
                    edges[M*ni+nj+1][M*i+j+1] = 0
        
        if S[i][j] == 'b':
            bc += 1
            edges[M*i+j+1][N*M+1] = 1
            edges[N*M+1][M*i+j+1] = 0

max_pair = max_flow(0, N*M+1)
wc -= max_pair
bc -= max_pair

print(max_pair*100+min(wc, bc)*10+abs(wc-bc))
0