311E - Biologist - CodeForces Solution

from collections import deque
from typing import List


class edge:
    
    
    def __init__(self, s: int, t: int, res: int):
        self.s = s
        self.t = t
        self.res = res
        self.reverse = None


def Dinic(net: List[List[edge]], s: int, t: int) -> int:
    
    ans = 0
    while True:
        q = deque()
        depth = [0] * (t - s + 10)
        mark = [0] * (t - s + 10)
        q.append(s)
        depth[s] = 1
                while q:
            cur = q.popleft()
            for e in net[cur]:
                if depth[e.t] == 0 and e.res > 0:
                    depth[e.t] = depth[cur] + 1
                    q.append(e.t)
            if depth[t] != 0:
                break
    
        if depth[t] == 0:
            return ans
    
        def dfs(now: int, flow: int) -> int:
            
            if now == t:
                return flow
            for i in range(mark[now], len(net[now])):
                e = net[now][i]
                if depth[e.t] == depth[now] + 1 and e.res > 0:
                    flowAdd = dfs(e.t, (flow if flow < e.res else e.res))
                    if flowAdd == 0:
                        continue
                    mark[now] = i
                    e.res -= flowAdd
                    e.reverse.res += flowAdd
                    return flowAdd
            return 0
        
        tmp = dfs(s, 2 ** 31 - 1)
        while tmp:
            ans += tmp
            tmp = dfs(s, 2 ** 31 - 1)
        
    return ans


def main():
    
    lenOfStr, numOfRequest, g = map(int, input().split())
    bitList = list(map(int, input().split()))
    v = list(map(int, input().split()))
            net = [list() for _ in range(lenOfStr + numOfRequest + 2)]
    
    def addEdge(s: int, t: int, res: int):
        
        e1 = edge(s, t, res)
        e2 = edge(t, s, 0)
        e1.reverse = e2
        e2.reverse = e1
        net[s].append(e1)
        net[t].append(e2)
    
    st = 0
    ed = lenOfStr + numOfRequest + 1
    for i, c in enumerate(v):
        if bitList[i] == 0:
            addEdge(st, i + 1, c)
        else:
            addEdge(i + 1, ed, c)
    
    inf = 2 ** 31 - 1
    ans = 0
    for i in range(numOfRequest):
        dataIn = list(map(int, input().split()))
        ans += dataIn[1]
        if dataIn[0] == 0:
            addEdge(st, lenOfStr + i + 1, dataIn[1] + (g if dataIn[-1] == 1 else 0))
            for j in range(dataIn[2]):
                addEdge(lenOfStr + i + 1, dataIn[j + 3], inf)
        else:
            addEdge(lenOfStr + i + 1, ed, dataIn[1] + (g if dataIn[-1] == 1 else 0))
            for j in range(dataIn[2]):
                addEdge(dataIn[j + 3], lenOfStr + i + 1, inf)

    print(ans - Dinic(net, st, ed))


if __name__ == '__main__':
    main()