Problem p02561 (python)

Fixed submission:

"""
sから奇数へ，奇数から偶数へ，偶数からtへ
"""
def main():
    # Dinic's algorithm
    import collections
    class Dinic:
        def __init__(self, vnum):
            self.edge = [[] for i in range(vnum)]
            self.n = vnum
            self.inf = 10**10
        def add_edge(self, start, end, c):
            self.edge[start].append([end, c, len(self.edge[end])])
            self.edge[end].append([start, 0, len(self.edge[start])-1])
        def bfs(self, vst):
            dist = [-1]*self.n
            dist[vst] = 0
            Q = collections.deque([vst])
            while Q:
                nv = Q.popleft()
                for vt, c, r in self.edge[nv]:
                    if dist[vt] == -1 and c > 0:
                        dist[vt] = dist[nv] + 1
                        Q.append(vt)
            self.dist = dist
        def dfs(self, nv, en, nf):
            nextv = self.nextv
            if nv == en:
                return nf
            dist = self.dist
            ist = nextv[nv]
            for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
                if dist[nv] < dist[vt] and c > 0:
                    df = self.dfs(vt, en, min(nf, c))
                    if df > 0:
                        self.edge[nv][i][1] -= df
                        self.edge[vt][r][1] += df
                        return df
                nextv[nv] += 1
            return 0
        def get_max_flow(self, st, en):
            mf = 0
            while True:
                self.bfs(st)
                if self.dist[en] == -1:
                    break
                self.nextv = [0]*self.n
                while True:
                    fl = self.dfs(st, en, self.inf)
                    if fl > 0:
                        mf += fl
                    else:
                        break
            return mf
        
    mod=10**9+7
    N,M=map(int, input().split())
    S=[]
    for _ in range(N):
        s=list(input())
        S.append(s)
        
    din=Dinic(N*M+2)
    s=N*M
    t=N*M+1
    
    # 場外との流路
    for i in range(N):
        for j in range(M):
            if S[i][j]=="#":
                continue
            v=M*i + j
            if (i+j)%2==1:
                din.add_edge(s,v,1)
            else:
                din.add_edge(v,t,1)
                
    # 場内
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    for i in range(N):
        for j in range(M):
            if S[i][j]=="#":
                continue
            v=M*i + j
            if (i+j)%2==1:
                for k in range(4):
                    ni=i+dx[k]
                    nj=j+dy[k]
                    
                    if 0<=ni<N and 0<=nj<M:
                        if S[ni][nj]== "#":
                            continue
                        nv=M*ni + nj
                        din.add_edge(v,nv,1)
                        
    
    ans=din.get_max_flow(s,t)
    
    T=[s[:] for s in S]
            
    
    for v in range(N*M):
        i,j = divmod(v,M)
        if (i+j)%2==1:
            if S[i][j]==".":
                for nv,cap,_ in din.edge[v]:
                    if cap==0 and nv!=t and nv!=s:#使った辺を見る
                        ni,nj=divmod(nv,M)
                        # print(i,j," ",ni,nj)
                        if i==ni:
                            if j<nj:
                                T[i][j]=">"
                                T[ni][nj]="<"
                            else:
                                T[i][j]="<"
                                T[ni][nj]=">"
                        else:
                            if i<ni:
                                T[i][j]="v"
                                T[ni][nj]="^"
                            else:
                                T[i][j]="^"
                                T[ni][nj]="v"
                                
                                
    print(ans)
    for i in range(N):
        print(''.join(map(str, T[i])))
                                
                                
                                
            
    
                    
        
    
    

main()

Buggy submission (verdict: Runtime Error):

"""
sから奇数へ，奇数から偶数へ，偶数からtへ
"""
def main():
    # Dinic's algorithm
    import collections
    class Dinic:
        def __init__(self, vnum):
            self.edge = [[] for i in range(vnum)]
            self.n = vnum
            self.inf = 10**10
        def add_edge(self, start, end, c):
            self.edge[start].append([end, c, len(self.edge[end])])
            self.edge[end].append([start, 0, len(self.edge[start])-1])
        def bfs(self, vst):
            dist = [-1]*self.n
            dist[vst] = 0
            Q = collections.deque([vst])
            while Q:
                nv = Q.popleft()
                for vt, c, r in self.edge[nv]:
                    if dist[vt] == -1 and c > 0:
                        dist[vt] = dist[nv] + 1
                        Q.append(vt)
            self.dist = dist
        def dfs(self, nv, en, nf):
            nextv = self.nextv
            if nv == en:
                return nf
            dist = self.dist
            ist = nextv[nv]
            for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
                if dist[nv] < dist[vt] and c > 0:
                    df = self.dfs(vt, en, min(nf, c))
                    if df > 0:
                        self.edge[nv][i][1] -= df
                        self.edge[vt][r][1] += df
                        return df
                nextv[nv] += 1
            return 0
        def get_max_flow(self, st, en):
            mf = 0
            while True:
                self.bfs(st)
                if self.dist[en] == -1:
                    break
                self.nextv = [0]*self.n
                while True:
                    fl = self.dfs(st, en, self.inf)
                    if fl > 0:
                        mf += fl
                    else:
                        break
            return mf
        
    mod=10**9+7
    N,M=map(int, input().split())
    S=[]
    for _ in range(N):
        s=list(input())
        S.append(s)
        
    din=Dinic(N*M+2)
    s=N*M
    t=N*M+1
    
    # 場外との流路
    for i in range(N):
        for j in range(M):
            if S[i][j]=="#":
                continue
            v=M*i + j
            if (i+j)%2==1:
                din.add_edge(s,v,1)
            else:
                din.add_edge(v,t,1)
                
    # 場内
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    for i in range(N):
        for j in range(M):
            if S[i][j]=="#":
                continue
            v=M*i + j
            if (i+j)%2==1:
                for k in range(4):
                    ni=i+dx[k]
                    nj=j+dy[k]
                    
                    if 0<=ni<N and 0<=nj<M:
                        if S[ni][nj]== "#":
                            continue
                        nv=M*ni + nj
                        din.add_edge(v,nv,1)
                        
    
    ans=din.get_max_flow(s,t)
    
    T=[s[:] for s in S]
            
    
    for v in range(N*M):
        if v%2==1:
            i,j = divmod(v,M)
            if S[i][j]==".":
                for nv,cap,_ in din.edge[v]:
                    if cap==0 and nv!=t:#使った辺を見る
                        ni,nj=divmod(nv,M)
                        # print(i,j," ",ni,nj)
                        if i==ni:
                            if j<nj:
                                T[i][j]=">"
                                T[ni][nj]="<"
                            else:
                                T[i][j]="<"
                                T[ni][nj]=">"
                        else:
                            if i<ni:
                                T[i][j]="v"
                                T[ni][nj]="^"
                            else:
                                T[i][j]="^"
                                T[ni][nj]="v"
                                
                                
    print(ans)
    for i in range(N):
        print(''.join(map(str, T[i])))
                                
                                
                                
            
    
                    
        
    
    

main()