結果

問題 No.654 Air E869120
コンテスト
ユーザー tonnnura172
提出日時 2020-05-14 01:58:59
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,449 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-09-14 15:48:38
合計ジャッジ時間 3,415 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 5
other RE * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
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)

def compress(A):
    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(A)):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped

N, M, d = MAP()

S = set()
edges = []
for _ in range(M):
    u, v, p, q, w = MAP()
    q += d
    u -= 1
    v -= 1
    S.add(p)
    S.add(q)
    edges.append((u, v, p, q, w))

zipped, _ = compress(S)

for i, (u, v, p, q, w) in enumerate(edges):
    p = zipped[p]
    q = zipped[q]
    edges[i] = (u, v, p, q, w)

L = len(zipped)  # フライトの時間の数
D = Dinic(N*L)
## N*Lのgridができる

A = [[] for _ in range(N)]
A[0].append(0)
for u, v, p, q, w in edges:
    D.add_edge(u*L+p, v*L+q, w)
    A[u].append(p)
    A[v].append(q)

for i in range(N):
    A[i].sort()
    for j in range(len(A[i])-1):
        p, q = A[i][j], A[i][j+1]
        D.add_edge(i*L+p, i*L+q, INF)

g = A[N-1][-1] if A[N-1] else 0
ans = D.max_flow(0, (N-1)*L+g)
print(ans)
0