Problem:

 

まるかいて

太郎君は小学生で、チラシの裏に落書きをしています。

ある時、太郎君は次のゲームを思いつきました。

n&times;nの格子状のマス目を書いておきます。

それぞれのマス目の初期状態は、丸印が書かれているか、書かれていないかのどちらか一方です。

これらの丸印を消したり書いたりして最終的にどの一列を見ても必ずちょうど1つのみの丸印が、どの一行を見ても必ず1つのみの丸印が存在するようにすることが目標であり、この状態にすればゲームをクリアしたことになります。

太郎君はこのゲームを思いつきましたが、太郎君はこのゲームをクリアするのに大変時間がかかってしまいます。そこで、大学生であるあなたに助けを求めました。

太郎君の兄であり大学生であるあなたの仕事は以下の通りです。

厳密な状況を考えるために、あるマス目に丸印を書き込むコスト、あるマス目にある丸印を消すコストをあなたは導き出しました。このコストを用いてこのゲームをクリアするためにかかる操作のコストを最小化するような手順を考える。
このとき、最小のコストおよびそのコストを達成するような手順を出力するプログラムを書いてください。
出力については、最小コストを達成する手順なら、どのような操作、順番でも出力してもよいものとする。

Input

n
W11 W12 .. W1n
W21 W22 .. W2n
..
Wn1 Wn2 .. Wnn
E11 E12 .. E1n
E21 E22 .. E2n
..
En1 En2 .. Enn
F1(n文字)
F2(n文字)
..
Fn(n文字)

nは太郎君の作ったマス目が一辺にいくつあるかを表す

Wijは上からi番目、左からj番目のマス目に丸印を書き込むコストを表す

Eijは上からi番目、左からj番目のマス目に書かれてある丸印を消すコストを表す

Fiは上からi番目の行のマス目の初期状態を表す

Fiの左からj文字目について

'o'のとき、上からi番目、左からj番目のマス目に丸印が書かれてあることを表す。

'.'のとき、上からi番目、左からj番目のマス目が空白であることを表す。

Constraints

1≤ n ≤ 100
1≤ Wij ≤ 1000
1≤ Eij ≤ 1000 

Fiは文字列であり、その長さはnである

Fiは'o'と'.'のみで構成されている

Output

mincost
cnt
R1 C1 operate1
R2 C2 operate2
..
Rcnt Ccnt operatecnt

mincostは、太郎君のゲームをクリアするために必要な最小コストを表す。

mincostは書き込み操作、消去操作で発生するコストの総和で計算される。

cnt : mincostのコストを達成する操作を行った回数を表す

k回目(1≤k≤cnt)に実行する操作はk+2行目に記述する

k回目(1≤k≤cnt)の操作に対して

上からi番目のマス目、左からj番目のマス目に対して行ったものとすると

Rkkである。

この操作が丸印を消す操作であるならばoperatek = "erase"とせよ

この操作が丸印を書き込む操作であるならばoperatek = "write"とせよ

Rk,Ck,operatekは一行に空白区切りで出力しなければならない

丸印の書かれてあるマス目に対して丸印を記述する操作、および丸印が書かれていないマス目に対して丸印を消去する操作をした場合はWrongAnswerである

cnt個の操作にかかるコストの総和がmincostに一致しないときはWrongAnswerである

Sample Input 1

3
1 1 1
1 1 1
1 1 1
1 1 1 
1 1 1
1 1 1
o.o
...
.o.

Output for the Sample Input 1

2
2
1 3 erase
2 3 write

上から1番目、左から3番目のマス目の丸印を消去し、
上から2番目、左から3番目のマス目に丸印を書き加えれば目標は達成できる。
このときコストは2のみしかかからず、これが最小のコストである。

Sample Input 2

4
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4
oooo
oooo
oooo
oooo

Output for the Sample Input 2

30
12
1 1 erase
1 2 erase
1 3 erase
2 1 erase
2 2 erase
2 4 erase
3 1 erase
3 3 erase
3 4 erase
4 2 erase
4 3 erase
4 4 erase

コスト(1+2+3+4)*3だけ消去処理をすればクリアとなります。

Sample Input 3

3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
o..
.o.
..o

Output for the Sample Input 3

0
0

すでに目標は達成されているため、コスト及び操作回数はともに0となる。



Sample input:
3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
o.o
...
.o.


Sample output:
2
2
1 3 erase
2 3 write

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Edge():
    def __init__(self,t,f,r,ca,co):
        self.to = t
        self.fron = f
        self.rev = r
        self.cap = ca
        self.cost = co

    def __str__(self):
        return f"Edge[{self.fron}, {self.to}, {self.rev}, {self.cap}, {self.cost}]"

class MinCostFlow():
    size = 0
    graph = []

    def __init__(self, s):
        self.size = s
        self.graph = [[] for _ in range(s)]

    def add_edge(self, f, t, ca, co):
        self.graph[f].append(Edge(t, f, len(self.graph[t]), ca, co))
        self.graph[t].append(Edge(f, t, len(self.graph[f])-1, 0, -co))

    def min_path(self, s, t):
        dist = [inf] * self.size
        route = [None] * self.size
        que = collections.deque()
        inq = [False] * self.size
        dist[s] = 0
        que.append(s)
        inq[s] = True
        while que:
            u = que.popleft()
            inq[u] = False
            for e in self.graph[u]:
                if e.cap == 0:
                    continue
                v = e.to
                if dist[v] > dist[u] + e.cost:
                    dist[v] = dist[u] + e.cost
                    route[v] = e
                    if not inq[v]:
                        que.append(v)
                        inq[v] = True

        if dist[t] == inf:
            return inf, 0

        flow = inf
        v = t
        while v != s:
            e = route[v]
            if flow > e.cap:
                flow = e.cap
            v = e.fron

        c = 0
        v = t
        while v != s:
            e = route[v]
            e.cap -= flow
            self.graph[e.to][e.rev].cap += flow
            c += e.cost * flow
            v = e.fron

        return dist[t], flow

    def calc_min_cost_flow(self, s, t, flow):
        total_cost = 0
        while flow > 0:
            c,f = self.min_path(s, t)
            if f == 0:
                return inf
            f = min(flow, f)
            total_cost += c * f
            flow -= f

        return total_cost


def main():
    n = I()
    wa = [LI() for _ in range(n)]
    ea = [LI() for _ in range(n)]
    fa = [[c == 'o' for c in S()] for _ in range(n)]

    s = n*2
    t = n*2 + 1
    mf = MinCostFlow(n*2+2)
    for i in range(n):
        mf.add_edge(s,i,1,0)
        mf.add_edge(i+n,t,1,0)
        fs = set([j for j in range(n) if fa[i][j]])
        fc = sum([ea[i][j] for j in fs])
        for j in range(n):
            if j in fs:
                mf.add_edge(i,j+n,1,fc-ea[i][j])
            else:
                mf.add_edge(i,j+n,1,fc+wa[i][j])

    r = mf.calc_min_cost_flow(s,t,n)
    ra = [[False]*n for _ in range(n)]
    for gr in mf.graph:
        for g in gr:
            if g.fron >= n or g.cap > 0:
                continue
            ra[g.fron][g.to-n] = True

    rr = []
    for i in range(n):
        for j in range(n):
            if fa[i][j] == ra[i][j]:
                continue
            if fa[i][j]:
                rr.append("{} {} erase".format(i+1, j+1))
            else:
                rr.append("{} {} write".format(i+1, j+1))

    return JA([r, len(rr)] + rr, "\n")

# start = time.time()
print(main())
# pe(time.time() - start)

Submission status: Accepted

Solution code:
import sys

from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write

    N = int(readline())
    W = [list(map(int, readline().split())) for i in range(N)]
    E = [list(map(int, readline().split())) for i in range(N)]
    F = [readline() for i in range(N)]
    mcf = MinCostFlow(2*N+2)
    for i in range(N):
        Wi = W[i]; Ei = E[i]; Fi = F[i]
        s0 = sum(Ei[j] for j in range(N) if Fi[j] == "o")
        for j in range(N):
            s = (s0 - Ei[j] if Fi[j] == "o" else s0 + Wi[j])
            mcf.add_edge(i, N+j, 1, s)
        mcf.add_edge(2*N, i, 1, 0)
        mcf.add_edge(N+i, 2*N+1, 1, 0)
    res = mcf.flow(2*N, 2*N+1, N)
    write("%d\n" % res)
    ans = []
    for i in range(N):
        Gi = mcf.G[i]
        Wi = W[i]; Ei = E[i]; Fi = F[i]
        for j in range(N):
            if Gi[j][1] == 0:
                for k in range(N):
                    if j == k or Fi[k] == ".":
                        continue
                    ans.append("%d %d erase" % (i+1, k+1))
                if Fi[j] == ".":
                    ans.append("%d %d write" % (i+1, j+1))
                break
    write("%d\n" % len(ans))
    if ans:
        write("\n".join(ans))
        write("\n")
solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class MinCostFlow:
    INF = 10 ** 18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):

        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            update = True

            while update:
                update = False
                for v in range(N):
                    if dist[v] == INF:
                        continue
                    for i, (to, cap, cost, _) in enumerate(G[v]):
                        if cap > 0 and dist[to] > dist[v] + cost:
                            dist[to] = dist[v] + cost
                            prv_v[to] = v; prv_e[to] = i
                            update = True
            if dist[t] == INF:
                return -1

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * dist[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

N = INT()
write = build_grid(N, N, 0, int)
erase = build_grid(N, N, 0, int)
grid = build_grid(N, N, '', str, space=0)

# 負のコストを扱うのでベルマンフォード版の最小費用流を使う
mcf = MinCostFlow(N*2+2)
s = N * 2
t = N * 2 + 1
erasesm = 0
for i in range(N):
    mcf.add_edge(s, i, 1, 0)
    mcf.add_edge(N+i, t, 1, 0)
    for j in range(N):
        if grid[i][j] == 'o':
            # 元々oの所は予め消したものとして、後で帳尻を合わせる
            erasesm += erase[i][j]
            mcf.add_edge(i, N+j, 1, -erase[i][j])
        else:
            mcf.add_edge(i, N+j, 1, write[i][j])

res = erasesm + mcf.flow(s, t, N)
written = set()
for fr in range(N):
    # fr(0~N-1)からto(N~N*2-1)を繋ぐ辺で、容量が0だったら使っているマスとみなせる
    for to, cap, cost, _ in mcf.G[fr]:
        if cap == 0 and N <= to < N*2:
            written.add((fr, to-N))
            break

ans = []
for i in range(N):
    for j in range(N):
        # 元々が書き込み済で結果が未記入なら消す操作
        if grid[i][j] == 'o' and (i, j) not in written:
            ans.append((i+1, j+1, 'erase'))
        # 元々が未記入で結果が書き込み済なら書く操作
        if grid[i][j] == '.' and (i, j) in written:
            ans.append((i+1, j+1, 'write'))
print(res)
print(len(ans))
for i, j, s in ans:
    print(i, j, s)