Contest Duration: ~ (local time)

Submission #7434067

Source Code Expand

Copy
```import sys
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
import itertools

# 二部グラフ完全マッチング

R,C = map(int,input().split())
R += 2
C += 2
if C%2 == 0:
C += 1
grid = '*' * C
row = row.rstrip()
grid += '*' + row + '*' * (C-1-len(row))
grid += '*' * C

# 頂点集合
V = set(i for i,x in enumerate(grid) if x == '.')
# 各頂点に対して、辞書(to:cap)を持たせる
source = 0
sink = -1
graph = defaultdict(dict)
for v in V:
if v%2 != 0:
graph[v][sink] = 1
graph[sink][v] = 0
continue
graph[source][v] = 1
graph[v][source] = 0
for dx in (1,-1,C,-C):
w = v+dx
if w not in V:
continue
# v to w でcap1の辺を貼る
graph[v][w] = 1
graph[w][v] = 0

def bfs():
level = defaultdict(int)
q = [source]
level[source] = 0
d = 0
while q:
if sink in level:
break
qq = []
d += 1
for v in q:
for w,cap in graph[v].items():
if cap == 0:
continue
if w in level:
continue
level[w] = d
qq.append(w)
q = qq
return level

def dfs(v,f,level,itr):
# 頂点vを見る。そこに来るまでだと f 流せる予定になっている
if v == sink:
return f
for w,cap in itr[v]:
if cap == 0 or level[w] != level[v] + 1:
continue
d = dfs(w,min(f,cap),level,itr)
if d:
# vからwにd流す
graph[v][w] -= d
graph[w][v] += d
return d
return 0

def max_flow():
INF = 10**18
flow = 0
while True:
level = bfs()
if level[sink] == 0:
break
itr = {v:iter(graph[v].items()) for v in V}
while True:
f = dfs(source,INF,level,itr)
if f == 0:
break
flow += f
return flow

f = max_flow()
```

#### Submission Info

Submission Time 2019-09-09 16:56:44+0900 C - 広告 maspy Python3 (3.4.3) 400 2235 Byte AC 41 ms 4464 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample0.txt, sample1.txt, sample2.txt, sample3.txt
All 400 / 400 01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
01-00.txt 21 ms 3316 KB
01-01.txt 34 ms 4336 KB
01-02.txt 21 ms 3316 KB
01-03.txt 28 ms 4208 KB
01-04.txt 41 ms 4464 KB
01-05.txt 29 ms 4080 KB
01-06.txt 37 ms 4336 KB
01-07.txt 21 ms 3316 KB
01-08.txt 36 ms 4336 KB
01-09.txt 39 ms 4464 KB
01-10.txt 31 ms 4208 KB
01-11.txt 21 ms 3316 KB
01-12.txt 34 ms 4336 KB
01-13.txt 39 ms 4336 KB
01-14.txt 26 ms 4080 KB
01-15.txt 39 ms 4336 KB
01-16.txt 21 ms 3316 KB
sample0.txt 22 ms 3316 KB
sample1.txt 21 ms 3316 KB
sample2.txt 21 ms 3316 KB
sample3.txt 21 ms 3316 KB