Submission #7434067


Source Code Expand

Copy
import sys
input = sys.stdin.readline
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
for row in sys.stdin.readlines():
    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
V.add(source)
V.add(sink)

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()
answer = len(V)-2-f
print(answer)

Submission Info

Submission Time
Task C - 広告
User maspy
Language Python3 (3.4.3)
Score 400
Code Size 2235 Byte
Status
Exec Time 41 ms
Memory 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