Problem:

Problem H: Ghost

Problem

  幽霊が一直線上に左から右に$N$人並んでいる。

  最初、左から$i$番目の幽霊は$U_i$が'L'ならば左を、'R'ならば右を向いている。

  彼らはとても臆病なのでなるべく怖い幽霊を見たくない。

あなたは、各幽霊に対して振り返るように指示をできる。

後ろを振り返るのは怖いので、$i$番目の幽霊が一回振り返ると$A_i$の恐怖度が発生する。

 左を向いている幽霊が振り返ると、右を向く。

 右を向いている幽霊が振り返ると、左を向く。

 $ i 
  
$U_i  = $'L' or 'R'

  
$1 \le A_i \le 1000$

  
$1 \le B_i \le 1000$

  
$1 \le S_i,T_i \le N$

  
$(S_i,T_i) \ne (S_j,T_j), $if $ i \ne j$

  
$S_i \ne T_i$

Output

  恐怖度の合計の最小値を出力せよ。

Sample Input 1

3 1
RRL
5 5 1
3 1 10

Sample Output 1

1

  3番目の幽霊に振り向くように指示をすると、恐怖度の合計は1となる。恐怖度の合計が0以下になるような指示は存在しないので、1を出力する。

Sample Input 2

5 5
RLRLL
9 5 1 3 10
1 3 5
2 4 9
4 2 16
1 5 2
3 5 10

Sample Output 2

8



Sample input:
3 1
RRL
5 5 1
3 1 10


Sample output:
1

Submission status: Accepted

Solution code:
from collections import deque

N,M = map(int,input().split())
U = input()
A = list(map(int,input().split()))
src = [tuple(map(int,input().split())) for i in range(M)]

edges = {}
for s,t,b in src:
    s,t = s-1,t-1
    if s>t: s,t = t,s
    if (s,t) in edges:
        edges[(s,t)] += b
    else:
        edges[(s,t)] = b

P = N+2
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])

for i,(u,a) in enumerate(zip(U,A)):
    if u == 'L':
        add_edge(0,i+2,a)
        add_edge(i+2,1,0)
    else:
        add_edge(0,i+2,0)
        add_edge(i+2,1,a)
for (s,t),b in edges.items():
    add_edge(t+2,s+2,b)

INF = float('inf')
level = [0] * P
iters = [0] * P

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(0,1))