結果
問題 | No.119 旅行のツアーの問題 |
ユーザー | rennnnn |
提出日時 | 2022-03-04 22:54:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 67 ms / 5,000 ms |
コード長 | 4,872 bytes |
コンパイル時間 | 907 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 67,584 KB |
最終ジャッジ日時 | 2024-07-18 21:29:26 |
合計ジャッジ時間 | 2,252 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 46 ms
54,784 KB |
testcase_01 | AC | 56 ms
64,512 KB |
testcase_02 | AC | 41 ms
54,272 KB |
testcase_03 | AC | 40 ms
54,272 KB |
testcase_04 | AC | 41 ms
54,400 KB |
testcase_05 | AC | 43 ms
55,040 KB |
testcase_06 | AC | 60 ms
65,792 KB |
testcase_07 | AC | 40 ms
54,528 KB |
testcase_08 | AC | 41 ms
54,272 KB |
testcase_09 | AC | 41 ms
54,400 KB |
testcase_10 | AC | 42 ms
54,784 KB |
testcase_11 | AC | 42 ms
54,656 KB |
testcase_12 | AC | 43 ms
54,656 KB |
testcase_13 | AC | 42 ms
54,528 KB |
testcase_14 | AC | 46 ms
55,040 KB |
testcase_15 | AC | 44 ms
54,784 KB |
testcase_16 | AC | 61 ms
65,408 KB |
testcase_17 | AC | 47 ms
54,784 KB |
testcase_18 | AC | 41 ms
54,784 KB |
testcase_19 | AC | 41 ms
54,656 KB |
testcase_20 | AC | 54 ms
63,488 KB |
testcase_21 | AC | 62 ms
65,664 KB |
testcase_22 | AC | 67 ms
67,584 KB |
ソースコード
#https://github.com/shakayami/ACL-for-python/wiki/maxflow #最大フロー問題 from collections import deque class mf_graph: n=1 g=[[] for i in range(1)] pos=[] def __init__(self,N): """初期化:Kはグラフの頂点数です。 初期化した直後は、頂点数Kで辺0のグラフとなります。""" self.n=N self.g=[[] for i in range(N)] self.pos=[] def add_edge(self,From,To,cap): """辺の追加:uからvへ、最大容量c,流量0の辺を追加します。""" assert 0<=From and From<self.n assert 0<=To and To<self.n assert 0<=cap m=len(self.pos) self.pos.append((From,len(self.g[From]))) self.g[From].append({"to":To,"rev":len(self.g[To]),"cap":cap}) self.g[To].append({"to":From,"rev":len(self.g[From])-1,"cap":0}) return m def get_edge(self,i): m=len(self.pos) assert 0<=i and i<m _e=self.g[self.pos[i][0]][self.pos[i][1]] _re=self.g[_e["to"]][_e["rev"]] return {"from":self.pos[i][0], "to":_e["to"], "cap":_e["cap"]+_re["cap"], "flow":_re["cap"]} def edges(self): """edges: for e in G.edges(): if e["flow"]==0: continue print(e) flowを実行した後には、どの辺にどれだけの流量が流れているかを示す値が残ります。 最大フローを求めた後、実際に最大となる状況を構成することが出来ます。 edgesはリストの形になっていて、リストの各要素はdictの構造を持っています。 そのdictにおいては、from,to,cap,flowという要素を持っています。これは、 from->toという辺を持っている。 最大流量capの辺にflowだけ辺が流れている という意味となっています。 """ m=len(self.pos) result=[] for i in range(m): result.append(self.get_edge(i)) return result def change_edge(self,i,new_cap,new_flow): m=len(self.pos) assert 0<=i and i<m assert 0<=new_flow and new_flow<=new_cap _e=self.g[self.pos[i][0]][self.pos[i][1]] _re=self.g[_e["to"]][_e["rev"]] _e["cap"]=new_cap-new_flow _re["cap"]=new_flow def flow(self,s,t,flow_limit=(1<<63)-1): """flow:sからtへの最大フローを求めます。""" assert 0<=s and s<self.n assert 0<=t and t<self.n level=[0 for i in range(self.n)] Iter=[0 for i in range(self.n)] que=deque([]) def bfs(): for i in range(self.n):level[i]=-1 level[s]=0 que=deque([]) que.append(s) while(len(que)>0): v=que.popleft() for e in self.g[v]: if e["cap"]==0 or level[e["to"]]>=0:continue level[e["to"]]=level[v]+1 if e["to"]==t:return que.append(e["to"]) def dfs(func,v,up): if (v==s):return up res=0 level_v=level[v] for i in range(Iter[v],len(self.g[v])): e=self.g[v][i] if (level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0):continue d=func(func,e["to"],min(up-res,self.g[e["to"]][e["rev"]]["cap"])) if d<=0:continue self.g[v][i]["cap"]+=d self.g[e["to"]][e["rev"]]["cap"]-=d res+=d if res==up:return res level[v]=self.n return res flow=0 while(flow<flow_limit): bfs() if level[t]==-1:break for i in range(self.n):Iter[i]=0 while(flow<flow_limit): f=dfs(dfs,t,flow_limit-flow) if not(f):break flow+=f return flow def min_cut(self,s): """最小カットが求められます。長さKのlistが返ってきます。""" visited=[False for i in range(self.n)] que=deque([]) que.append(s) while(len(que)>0): p=que.popleft() visited[p]=True for e in self.g[p]: if e["cap"] and not(visited[e["to"]]): visited[e["to"]]=True que.append(e["to"]) return visited n = int(input()) mf = mf_graph(2*n+2) INF = 10**9 tot = 0 s = 2*n t = 2*n+1 for i in range(n): a,b = list(map(int, input().split())) mf.add_edge(s,2*i,b) mf.add_edge(2*i,2*i+1,a+b) mf.add_edge(2*i+1,t,a) tot += a+b m = int(input()) for i in range(m): d,e = list(map(int, input().split())) mf.add_edge(e*2+1,d*2,INF) ans = tot-mf.flow(s,t) print(ans)