結果
問題 |
No.3173 じゃんけんの勝ちの回数
|
ユーザー |
👑 |
提出日時 | 2025-06-06 22:41:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 694 ms / 2,000 ms |
コード長 | 5,097 bytes |
コンパイル時間 | 428 ms |
コンパイル使用メモリ | 82,968 KB |
実行使用メモリ | 98,808 KB |
最終ジャッジ日時 | 2025-06-06 22:41:30 |
合計ジャッジ時間 | 21,379 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
from collections import deque class mf_graph: n=0 g=[] def __init__(self,n_): self.n=n_ self.g=[[] for i in range(self.n)] self.pos=[] class _edge: to=0 rev=0 cap=0 def __init__(self,to_,rev_,cap_): self.to=to_ self.rev=rev_ self.cap=cap_ class edge: From=0 To=0 Cap=0 Flow=0 def __init__(self,from_,to_,cap_,flow_): self.From=from_ self.To=to_ self.Cap=cap_ self.Flow=flow_ def add_edge(self,From_,To_,Cap_): 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_]))) from_id=len(self.g[From_]) to_id=len(self.g[To_]) if (From_==To_):to_id+=1 self.g[From_].append(self._edge(To_,to_id,Cap_)) self.g[To_].append(self._edge(From_,from_id,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 self.edge(self.pos[i][0],_e.to,_e.cap+_re.cap,_re.cap) def edges(self,isdict=True): m=len(self.pos) result=[] for i in range(m): if isdict: e=self.get_edge(i) result.append({"from":e.From,"to":e.To,"cap":e.Cap,"flow":e.Flow}) else: 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[pos[i][0]][pos[i][1]] _re=self.g[_e.to][_e.rev] _e.cap=new_cap-new_flow _re.cap=new_flow assert id(_e)==id(self.g[self.pos[i][0]][self.pos[i][1]]) assert id(_re)==id(self.g[_e.to][_e.rev]) def flow(self,s,t,flow_limit=(1<<63)-1): assert 0<=s and s<self.n assert 0<=t and t<self.n assert s!=t 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.clear() que.append(s) while(que): 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(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] assert id(e)==id(self.g[v][i]) if level_v<=level[e.to] or self.g[e.to][e.rev].cap==0: continue d=dfs(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 Iter=[0 for i in range(self.n)] f=dfs(t,flow_limit-flow) if not(f): break flow+=f return flow def min_cut(self,s): visited=[False for i in range(self.n)] que=deque([s]) while(que): 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 def solve(): A = list(map(int, input().split())) B = list(map(int, input().split())) def solve_min(A, B): mf = mf_graph(2 + len(A) + len(B)) mf.add_edge(0, 1, A[0]) mf.add_edge(0, 2, A[1]) mf.add_edge(0, 3, A[2]) mf.add_edge(1, 4, B[0]) mf.add_edge(2, 4, B[0]) mf.add_edge(2, 5, B[1]) mf.add_edge(3, 5, B[1]) mf.add_edge(1, 6, B[2]) mf.add_edge(3, 6, B[2]) mf.add_edge(4, 7, B[0]) mf.add_edge(5, 7, B[1]) mf.add_edge(6, 7, B[2]) return sum(B) - mf.flow(0, 7) def solve_max(A, B): mf = mf_graph(2 + len(A) + len(B)) mf.add_edge(0, 1, A[0]) mf.add_edge(0, 2, A[1]) mf.add_edge(0, 3, A[2]) mf.add_edge(3, 4, B[0]) mf.add_edge(1, 5, B[1]) mf.add_edge(2, 6, B[2]) mf.add_edge(4, 7, B[0]) mf.add_edge(5, 7, B[1]) mf.add_edge(6, 7, B[2]) return mf.flow(0, 7) print(solve_min(A, B), solve_max(A, B)) if __name__ == "__main__": T = int(input()) for _ in range(T): solve()