Problem:


Score : 800 points

Problem Statement

There is a pond with a rectangular shape.
The pond is divided into a grid with H rows and W columns of squares.
We will denote the square at the i-th row from the top and j-th column from the left by (i,\ j).

Some of the squares in the pond contains a lotus leaf floating on the water.
On one of those leaves, S, there is a frog trying to get to another leaf T.
The state of square (i,\ j) is given to you by a character a_{ij}, as follows:

. : A square without a leaf.

o : A square with a leaf floating on the water.

S : A square with the leaf S.

T : A square with the leaf T.

The frog will repeatedly perform the following action to get to the leaf T: "jump to a leaf that is in the same row or the same column as the leaf where the frog is currently located."

Snuke is trying to remove some of the leaves, other than S and T, so that the frog cannot get to the leaf T.
Determine whether this objective is achievable. If it is achievable, find the minimum necessary number of leaves to remove.

Constraints

2 ≤ H, W ≤ 100

a_{ij} is ., o, S or T.

There is exactly one S among a_{ij}.

There is exactly one T among a_{ij}.

Input

Input is given from Standard Input in the following format:

H W
a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}

Output

If the objective is achievable, print the minimum necessary number of leaves to remove.
Otherwise, print -1 instead.

Sample Input 1

3 3
S.o
.o.
o.T

Sample Output 1

2

Remove the upper-right and lower-left leaves.

Sample Input 2

3 4
S...
.oo.
...T

Sample Output 2

0

Sample Input 3

4 3
.S.
.o.
.o.
.T.

Sample Output 3

-1

Sample Input 4

10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo

Sample Output 4

5



Sample input:
3 3
S.o
.o.
o.T


Sample output:
2

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000)
    # 行先、上限、逆辺

    def add_edge(From, to, cap):
        g[From][to] = cap
        g[to][-From-1] = 0

    def max_flow(s, t):
        def dfs(v, t, f):
            q.append(v)
            if v == t:
                return f
            used[v] += 1
            for i in range(len(gkey[v])):
                to = gkey[v][i]
                cap = g[v][to]
                if to < 0:
                    to2 = -to-1
                else:
                    to2 = to
                if used[to2] or cap == 0:
                    continue
                d = dfs(to2, t, min(f, cap))
                if d > 0:
                    g[v][to] -= d
                    g[to2][-v-1] += d
                    return d
            q.pop()
            return 0

        flow = 0
        while True:
            used = [0]*n
            q = []
            f = dfs(s, t, 10**100)
            if not q:
                return flow
            flow += f

    h, w = map(int, input().split())
    n = h+w+2
    g = [dict() for _ in range(n)]
    for i in range(h):
        A = input()
        for j in range(w):
            if A[j] == "o":
                add_edge(i, j+h, 1)
                add_edge(j+h, i, 1)
            elif A[j] == "S":
                add_edge(h+w, i, 10**6)
                add_edge(h+w, j+h, 10**6)
            elif A[j] == "T":
                add_edge(i, h+w+1, 10**6)
                add_edge(j+h, h+w+1, 10**6)
    gkey = [list(i.keys()) for i in g]

    ans = max_flow(h+w, h+w+1)
    if ans >= 10**6:
        print(-1)
    else:
        print(ans)


main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:
    def __init__(self, v, inf =10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v  # 深さ
        self.ite = [0]*v  # DFSでの探索が済んでいるか
    def add_edge(self, fr, to, cap):
        self.G[fr].append([to, cap, len(self.G[to])])
        self.G[to].append([fr, 0, len(self.G[fr])-1])
    def bfs(self, s):  # BFSで深さ決定,sがstart
        self.level = [-1]*self.v  # 必要
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1]>0 and self.level[e[0]]<0: ###capacity>0かつtoの深さ未定
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])
    def dfs(self, v, t, f):  # DFSで増加パス探索,v開始、t終点、総フローf
        if v==t:
            return f
        for i in range(self.ite[v],len(self.G[v])):
            self.ite[v] = i
            e = self.G[v][i]
            if e[1]>0 and self.level[v]<self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d  # cap減少
                    self.G[e[0]][e[2]][1] += d  # 逆辺のcap増加
                    return d
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0:
                return flow
            self.ite = [0]*self.v  # DFSでの探索が済んでいるか否か
            f =self.dfs(s,t,self.inf)
            while f>0:
                flow+= f
                f = self.dfs(s,t,self.inf)

H, W = MAP()
a = [list(input()) for _ in range(H)]
D = Dinic(H+W+2)

for i in range(H):
    for j in range(W):
        if a[i][j] == "S":
            sy, sx = i, j
            D.add_edge(0, i+1, INF)
            D.add_edge(0, H+j+1, INF)
        elif a[i][j] == "T":
            gy, gx = i, j
            D.add_edge(i+1, H+W+1, INF)
            D.add_edge(H+j+1, H+W+1, INF)
        elif a[i][j] == "o":
            D.add_edge(i+1, H+j+1, 1)
            D.add_edge(H+j+1, i+1, 1)

if sy == gy or sx == gx:
	print(-1)
	exit()

print(D.max_flow(0, H+W+1))

Submission status: Accepted

Solution code:
def dfs(v,t,f,used,graph):
    if v==t:
        return f
    used[v] = True
    for to in graph[v]:
        c = graph[v][to]
        if used[to] or c==0:
            continue
        d = dfs(to,t,min(f,c),used,graph)
        if d>0:
            graph[v][to] -= d
            graph[to][v] += d
            return d
    return 0
 
def max_flow(s,t,graph):
    flow = 0
    while True:
        used = [False]*len(graph)
        f = dfs(s,t,float('inf'),used,graph)
        flow += f
        if f==0 or f==float('inf'):
            return flow
 
H,W = map(int,input().split())

a = [input() for _ in range(H)]
a = [[s for s in a[i]] for i in range(H)]

graph = [{} for _ in range(H+W+2)]

for h in range(H):
    for w in range(W):
        if a[h][w]=='o':
            graph[h][H+w] = 1
            graph[H+w][h] = 1
        if a[h][w]=='S':
            graph[H+W][h] = float('inf')
            graph[H+W][H+w] = float('inf')
            graph[h][H+W] = 0
            graph[H+w][H+W] = 0
        if a[h][w]=='T':
            graph[H+W+1][h] = 0
            graph[H+W+1][H+w] = 0
            graph[h][H+W+1] = float('inf')
            graph[H+w][H+W+1] = float('inf')

ans = max_flow(H+W,H+W+1,graph)
if ans == float('inf'):
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [input() for i in range(H)]
sy = sx = ty = tx = -1
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c=='S':
            sy,sx = i,j
        if c=='T':
            ty,tx = i,j
if sy==ty or sx==tx:
    print(-1)
    exit()

S = H+W
G = S+1
P = G+1
es = [[] for i in range(P)] # [[to1,cap1,rev1], ...]

def add_edge(fr,to,cap):
    es[fr].append([to,cap,len(es[to])])
    es[to].append([fr,0,len(es[fr])-1])
INF = float('inf')
add_edge(S, sy, INF)
add_edge(S, H+sx, INF)
add_edge(ty, G, INF)
add_edge(H+tx, G, INF)
for i,row in enumerate(A):
    for j,c in enumerate(row):
        if c!='o': continue
        add_edge(i, H+j, 1)
        add_edge(H+j, i, 1)

level = [0] * P
iters = [0] * P
from collections import deque
def dinic_max_flow(s,t):
    global iters

    def _bfs(s):
        global level
        level = [-1] * P
        level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for to,cap,rev in es[v]:
                if cap > 0 and level[to] < 0:
                    level[to] = level[v] + 1
                    q.append(to)

    def _dfs(v,t,f):
        if v == t: return f
        for i in range(iters[v],len(es[v])):
            iters[v] += 1
            to,cap,rev = es[v][i]
            if es[v][i][1] > 0 and level[v] < level[to]:
                d = _dfs(to,t,min(f,es[v][i][1]))
                if d > 0:
                    es[v][i][1] -= d #cap
                    es[to][rev][1] += d
                    return d
        return 0

    flow = 0
    while True:
        _bfs(s)
        if level[t] < 0: return flow
        iters = [0] * P
        f = 0
        while True:
            f = _dfs(s,t,INF)
            if f <= 0: break
            flow += f

print(dinic_max_flow(S,G))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class Dinic():
    def __init__(self, G, source, sink):
        self.G = G
        self.sink = sink
        self.source = source

    def add_edge(self, u, v, cap):
        self.G[u][v] = cap
        self.G[v][u] = 0

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

    def dfs(self, u, f):
        if u == self.sink:
            return f
        for v, cap in self.iter[u]:
            if cap == 0 or self.level[v] != self.level[u] + 1:
                continue
            d = self.dfs(v, min(f, cap))
            if d:
                self.G[u][v] -= d
                self.G[v][u] += d
                return d
        return 0

    def max_flow(self):
        flow = 0
        while True:
            self.bfs()
            if self.level[self.sink] == 0:
                break
            self.iter = {u: iter(self.G[u].items()) for u in self.G}
            while True:
                f = self.dfs(self.source, INF)
                if f == 0:
                    break
                flow += f
        return flow

h, w = LI()
s = SR(h)
G = defaultdict(lambda:defaultdict(int))
for i in range(h):
    for j in range(w):
        if s[i][j] == 'o':
            G[i][h + j] = 1
            G[h + j][i] = 1
        elif s[i][j] == 'S':
            G[h + w][i] = INF
            G[h + w][h + j] = INF
        elif s[i][j] == 'T':
            G[i][h + w + 1] = INF
            G[h + j][h + w + 1] = INF

ans = Dinic(G, h + w, h + w + 1).max_flow()
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class Dinic:
    def __init__(self, n):
        self.n = n
        self.G = [[] for _ in range(n)]
        self.level = None
        self.it = None

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [-1] * self.n
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] == -1:
                    level[w] = lv
                    deq.append(w)
        return level[t] != -1

    def dfs(self, v, t, f):
        if v == t:
            return f
        for e in self.it[v]:
            w, cap, rev = e
            if cap and self.level[v] < self.level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10 ** 18
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

h, w = LI()
dinic = Dinic(h + w + 2)
s = SR(h)
for i in range(h):
    for j in range(w):
        if s[i][j] == 'o':
            dinic.add_multi_edge(i, h + j, 1, 1)
        elif s[i][j] == 'S':
            dinic.add_edge(h + w, i, INF)
            dinic.add_edge(h + w, h + j, INF)
        elif s[i][j] == 'T':
            dinic.add_edge(i, h + w + 1, INF)
            dinic.add_edge(h + j, h + w + 1, INF)

ans = dinic.flow(h + w, h + w + 1)
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.level = None
        self.it = None
    
    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.graph[fr].append(forward)
        self.graph[to].append(backward)
    
    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.graph[v1].append(edge1)
        self.graph[v2].append(edge2)
    
    def bfs(self, s, t):
        self.level = level = [-1] * self.n
        deq = deque([s])
        level[s] = 0
        G = self.graph
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] == -1:
                    level[w] = lv
                    deq.append(w)
        return level[t] != -1
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        for e in self.it[v]:
            w, cap, rev = e
            if cap and self.level[v] < self.level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0
    
    def flow(self, s, t):
        flow = 0
        INF = 10 ** 18
        while self.bfs(s, t):
            *self.it, = map(iter, self.graph)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


def solve():
    H, W = map(int, rl().split())
    INF = 10 ** 18
    s = H + W
    t = s + 1
    dinic = Dinic(t + 1)
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == 'o':
                dinic.add_multi_edge(i, H + j, 1, 1)
            elif line[j] == 'S':
                dinic.add_edge(s, i, INF)
                dinic.add_edge(s, H + j, INF)
            elif line[j] == 'T':
                dinic.add_edge(i, t, INF)
                dinic.add_edge(H + j, t, INF)
    
    ans = dinic.flow(s, t)
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# https://tjkendev.github.io/procon-library/python/max_flow/dinic.html
from collections import deque
class Dinic:
	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def add_bidirectional_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.g[v1].append(edge1)
		self.g[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None]*self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for w, cap, _ in g[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			w, cap, rev = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10**30
		g = self.g
		while self.bfs(s, t):
			*self.it, = map(iter, self.g)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

H, W = map(int, input().split())
a = [input() for _ in range(H)]
d = Dinic(H+W+2)
for i in range(H):
	for j in range(W):
		if a[i][j] == "S":
			d.add_edge(H+W, i, 10**5)
			d.add_edge(H+W, H+j, 10**5)
		elif a[i][j] == "T":
			d.add_edge(i, H+W+1, 10**5)
			d.add_edge(H+j, H+W+1, 10**5)
		elif a[i][j] == "o":
			d.add_edge(i, H+j, 1)
			d.add_edge(H+j, i, 1)
ans = d.flow(H+W, H+W+1)
if ans > 10000:
	print(-1)
else:
	print(ans)

Submission status: Accepted

Solution code:
#ARC074-F Lotus Leaves
"""
この問題は最小カットに帰着できる。但し、h*wの頂点を持つと間に合わないので、H軸とW軸を独立に考える。
縦H個、横W個の頂点を持つ。
ある座標h,wがoの時、頂点H[h]とW[w]と容量1のネットワークでつなぐ。[sourse,h0,h1,...hH,w0,w1,...wW,sink]
startとgoalを最大流の始点、終点として持つのではなく、それとは別にsourse,sinkの2頂点を作る。
startとsourse,goalとsinkを容量INFでつなぐことにより、より簡単に最小カットを求めることが可能になる。
よって、グラフ長はH*W+2となる。
ネットワーク自体は無向なので、undirectedを使用する。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#maspyさんの方(sourceとsinkを追加する方法)
"""
class Dinicの使い方:
initは、Dinic(頂点数,始点,終点)で行う。
最大流の典型として、実際に問題に与えられる始点、終点とは別に、その始点sと終点tを、
新たに作成したsource(S)とsink(T)にcap=INFでつなげることで、実質始点と終点をそのままで使用することができる。
このテクニックにより簡単になる問題が多いので、いっそそれを前提にしちゃえというのがこのテンプレ。
与えられるグラフの頂点数をNとして、N+2(sourceとsinkの+2)で初期化し、source=0,sink=N+1とすると良い。
辺を張る際に、
有向グラフの場合は、add_edge(from,to,capacity)
無向グラフの場合は、add_edge_undirected(from,to,capacity)　とする。
最後にmax_flowで最大流を求めるが、INFが10**18と非常に大きいのは、sourceからsinkへのパスが存在しなかった場合、
INF以上の値が帰ってくる為である。
「もしそのような最大流が存在しないなら-1を出力」というような条件で、
f = max_flow()
if f == INF:
    print(-1)
とやると、fがINFより大きい場合があるので、
if f >= INF:
    print(-1)
else:
    print(f)
とする必要がある。 
"""
from collections import deque
class Dinic():
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink
 
    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) # 逆辺を cap 0 で追加
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1]) # 逆辺を cap capで追加
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        G = self.G
        prog = self.progress
        level = self.level
        lv = level[v]
        E = G[v]
        for i in range(prog[v],len(E)):
            to, cap, rev = E[i]
            prog[v] = i
            if not cap:
                continue
            if level[to] <= lv:
                continue
            x = f if f < cap else cap
            ff = self.dfs(to, x)
            if ff:
                E[i][1] -= ff
                G[to][rev][1] += ff
                return ff
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs(self.source, INF)
                if not f:
                    break
                flow += f
        return flow

H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

source = 0
sink = H+W+1
network = Dinic(H+W+2,source,sink)
INF = 10**18

for i in range(1,H+1):
    for j,ox in enumerate(maze[i-1],1):
        if ox == "x":
            continue
        elif ox == "o":
            network.add_edge_undirected(i,H+j,1)
        elif ox == "S":
            network.add_edge_undirected(source,i,INF)
            network.add_edge_undirected(source,H+j,INF)
        elif ox == "T":
            network.add_edge_undirected(i,sink,INF)
            network.add_edge_undirected(H+j,sink,INF)

f = network.max_flow()
if f >= INF:
    print(-1)
else:
    print(f)

Submission status: Accepted

Solution code:
#ARC074-F Lotus Leaves
"""
この問題は最小カットに帰着できる。但し、h*wの頂点を持つと間に合わないので、H軸とW軸を独立に考える。
縦H個、横W個の頂点を持つ。
ある座標h,wがoの時、頂点H[h]とW[w]と容量1のネットワークでつなぐ。[sourse,h0,h1,...hH,w0,w1,...wW,sink]
startとgoalを最大流の始点、終点として持つのではなく、それとは別にsourse,sinkの2頂点を作る。
startとsourse,goalとsinkを容量INFでつなぐことにより、より簡単に最小カットを求めることが可能になる。
よって、グラフ長はH*W+2となる。
ネットワーク自体は無向なので、undirectedを使用する。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

from collections import deque

class Dinic():
    def __init__(self, N, source, sink):
        self.N = N
        self.G = [[] for _ in range(N)]
        self.source = source
        self.sink = sink
 
    def add_edge(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, 0, n1]) # 逆辺を cap 0 で追加
        
    def add_edge_undirected(self, fr, to, cap):
        n1 = len(self.G[fr])
        n2 = len(self.G[to])
        self.G[fr].append([to, cap, n2])
        self.G[to].append([fr, cap, n1]) # 逆辺を cap 0 で追加
        
    def bfs(self):
        level = [0] * self.N
        G = self.G; source = self.source; sink = self.sink
        q = deque([source])
        level[source] = 1
        pop = q.popleft; append = q.append
        while q:
            v = pop()
            lv = level[v] + 1
            for to, cap, rev in G[v]:
                if not cap:
                    continue
                if level[to]:
                    continue
                level[to] = lv
                if to == sink:
                    self.level = level
                    return
                append(to)
        self.level = level
        
    def dfs(self,v,f):
        if v == self.sink:
            return f
        G = self.G
        prog = self.progress
        level = self.level
        lv = level[v]
        E = G[v]
        for i in range(prog[v],len(E)):
            to, cap, rev = E[i]
            prog[v] = i
            if not cap:
                continue
            if level[to] <= lv:
                continue
            x = f if f < cap else cap
            ff = self.dfs(to, x)
            if ff:
                E[i][1] -= ff
                G[to][rev][1] += ff
                return ff
        return 0
    
    def max_flow(self):
        INF = 10**18
        flow = 0
        while True:
            self.bfs()
            if not self.level[self.sink]:
                return flow
            self.progress = [0] * self.N
            while True:
                f = self.dfs(self.source, INF)
                if not f:
                    break
                flow += f
        return flow

H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

source = 0
sink = H+W+1
network = Dinic(H+W+2,source,sink)
INF = 10**18

for i in range(1,H+1):
    for j,ox in enumerate(maze[i-1],1):
        if ox == "x":
            continue
        elif ox == "o":
            network.add_edge_undirected(i,H+j,1)
        elif ox == "S":
            network.add_edge_undirected(source,i,INF)
            network.add_edge_undirected(source,H+j,INF)
        elif ox == "T":
            network.add_edge_undirected(i,sink,INF)
            network.add_edge_undirected(H+j,sink,INF)

f = network.max_flow()
if f >= INF:
    print(-1)
else:
    print(f)

Submission status: Accepted

Solution code:
# Dinic's algorithm
from collections import deque


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

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


h, w = map(int, input().split())
dinic = Dinic((h+1)*(w+1))
maze = [list(input()) for _ in range(h)]
start = 0
goal = 0
INF = 10 ** 9 + 7

for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            continue
        if maze[i][j] == 'S':
            start = (i + 1) * (w + 1) + j + 1
            dinic.add_edge(start, j + 1, INF)
            dinic.add_edge(start, (i+1)*(w+1), INF)
        elif maze[i][j] == 'T':
            goal = (i + 1) * (w + 1) + j + 1
            dinic.add_edge(j + 1, goal, INF)
            dinic.add_edge((i+1)*(w+1), goal, INF)
        dinic.add_multi_edge(j + 1, (i + 1) * (w + 1) + j + 1, 1, 1)
        dinic.add_multi_edge((i+1)*(w+1), (i+1)*(w+1) + j+1, 1, 1)
ans = dinic.flow(start, goal)
print(ans if ans < 10**9 else -1)