結果
問題 | No.654 Air E869120 |
ユーザー | りん |
提出日時 | 2023-07-09 17:02:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 254 ms / 2,000 ms |
コード長 | 3,572 bytes |
コンパイル時間 | 747 ms |
コンパイル使用メモリ | 87,160 KB |
実行使用メモリ | 187,020 KB |
最終ジャッジ日時 | 2023-09-30 20:27:43 |
合計ジャッジ時間 | 9,096 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 99 ms
71,684 KB |
testcase_01 | AC | 97 ms
71,492 KB |
testcase_02 | AC | 98 ms
71,424 KB |
testcase_03 | AC | 100 ms
71,776 KB |
testcase_04 | AC | 99 ms
71,588 KB |
testcase_05 | AC | 97 ms
71,436 KB |
testcase_06 | AC | 104 ms
76,488 KB |
testcase_07 | AC | 97 ms
71,428 KB |
testcase_08 | AC | 97 ms
71,668 KB |
testcase_09 | AC | 97 ms
71,596 KB |
testcase_10 | AC | 236 ms
78,984 KB |
testcase_11 | AC | 219 ms
79,448 KB |
testcase_12 | AC | 222 ms
79,248 KB |
testcase_13 | AC | 232 ms
79,468 KB |
testcase_14 | AC | 205 ms
79,356 KB |
testcase_15 | AC | 202 ms
79,028 KB |
testcase_16 | AC | 247 ms
113,984 KB |
testcase_17 | AC | 246 ms
114,000 KB |
testcase_18 | AC | 254 ms
114,472 KB |
testcase_19 | AC | 243 ms
113,752 KB |
testcase_20 | AC | 194 ms
110,724 KB |
testcase_21 | AC | 205 ms
119,696 KB |
testcase_22 | AC | 162 ms
90,756 KB |
testcase_23 | AC | 171 ms
94,292 KB |
testcase_24 | AC | 214 ms
116,472 KB |
testcase_25 | AC | 156 ms
86,928 KB |
testcase_26 | AC | 167 ms
91,888 KB |
testcase_27 | AC | 145 ms
83,888 KB |
testcase_28 | AC | 178 ms
101,092 KB |
testcase_29 | AC | 145 ms
84,144 KB |
testcase_30 | AC | 244 ms
186,828 KB |
testcase_31 | AC | 247 ms
186,684 KB |
testcase_32 | AC | 247 ms
187,020 KB |
testcase_33 | AC | 231 ms
139,844 KB |
testcase_34 | AC | 244 ms
186,764 KB |
testcase_35 | AC | 98 ms
71,640 KB |
testcase_36 | AC | 98 ms
71,812 KB |
testcase_37 | AC | 99 ms
71,528 KB |
testcase_38 | AC | 99 ms
71,628 KB |
testcase_39 | AC | 102 ms
71,680 KB |
ソースコード
#https://yukicoder.me/problems/no/654 import sys sys.setrecursionlimit(10**7) from collections import deque class Edmond_karp: def __init__(self,V): self.v = V self.edges = [[] for _ in range(V)] #隣接リスト def addEdge(self,fr,to,cap): forward = [to,cap,len(self.edges[to])] #行き先、capasity,逆向きの辺のindex backward = [fr,0,len(self.edges[fr])] #逆向きの辺 self.edges[fr].append(forward) self.edges[to].append(backward) def bfs(self,s,t): #tはdestination,fは追加できる最大のフロー量 q = deque([(s,-1,float('inf'),-1)]) #vertex,parent,flow,rev_idx parent = [-1]*self.v revs = [-1]*self.v self.used[s] = 1 parent[s] = -1 revs[s] = -1 #sからでてる逆向きの辺は存在しないので-1でok aug_flow = 0 #sからtまでの最短距離を計算する while len(q) > 0: v,p,f,rev = q.popleft() if v == t: #終点に達したら aug_flow = f break for e in self.edges[v]: w,cap,rev_idx = e #revは反対の辺の情報 if cap and not self.used[w]: q.append((w,v,min(f,cap),rev_idx)) self.used[w] = 1 parent[w] = v revs[w] = rev_idx #wの逆向きの辺のindex # 最短経路のフロー数だけ遡る if aug_flow: #最大値が0じゃなかったら v,p,rev = t,parent[t],revs[t] while p != -1: rev_e = self.edges[v][rev] #tからのreversed edge e = self.edges[p][rev_e[2]] #vじゃだめ。index入れないと e[1] -= aug_flow rev_e[1] += aug_flow v,p,rev = p,parent[p],revs[p] return aug_flow def flow(self,s,t): flow = 0 f = INF = float('inf') v = self.v while f: #この操作回数はO(VE)らしい。 self.used = [0]*v #used初期化 f = self.bfs(s,t) #計算量はO(E) fordfulkersonと一緒 flow += f return flow N,M,d = map(int,input().split()) #(u,pi)→(v,qi)にcapacityがwiの辺を設定 #(u,pi)→(u,pi+1)には容量無限大の辺を設定(空港で待つことを意味する) #上の方法だと間に合わないから #辺を貼るのは街iに飛行機が到着する時刻だけでいい。 def convert(u,time): return u*maxtime + time_dict[time] INF = float('inf') #dを考慮する。Aに出発しBに到着する飛行機はAに出発し、B+dに到着するとみなすことができる。 events = [] time = set() for _ in range(M): u,v,p,q,w = map(int,input().split()) #このqは1日の終わりを超えることはない。 u -= 1 v -= 1 q += d #(u,p)→(v,q+d)へcapacityがwの辺 events.append((u,v,p,q,w)) time.add(p) time.add(q) time = sorted(list(time)) maxtime = len(time) time_dict = {t:i for i,t in enumerate(time)} ff = Edmond_karp(maxtime*N) wait = [[] for _ in range(N)] for u,v,p,q,w in events: ff.addEdge(convert(u,p),convert(v,q),w) wait[u].append(p) wait[v].append(q) for i in range(N): wait[i].sort() for j in range(len(wait[i])-1): t1 = wait[i][j] t2 = wait[i][j+1] ff.addEdge(convert(i,t1),convert(i,t2),INF) if wait[0] and wait[N-1]: print(ff.flow(convert(0,wait[0][0]),convert(N-1,wait[N-1][-1]))) else: print(0)