結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
![]() |
提出日時 | 2023-08-29 14:55:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 3,570 bytes |
コンパイル時間 | 418 ms |
コンパイル使用メモリ | 82,348 KB |
実行使用メモリ | 69,080 KB |
最終ジャッジ日時 | 2024-12-30 23:32:05 |
合計ジャッジ時間 | 1,777 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
from collections import dequeclass mf_graph:n=1g=[[] for i in range(1)]pos=[]def __init__(self,N):self.n=Nself.g=[[] for i in range(N)]self.pos=[]def add_edge(self,From,To,cap):assert 0<=From and From<self.nassert 0<=To and To<self.nassert 0<=capm=len(self.pos)from_id=len(self.g[From])self.pos.append([From,from_id])to_id=len(self.g[To])if From==To:to_id+=1self.g[From].append([To,to_id,cap])self.g[To].append([From,from_id,0])return mdef 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[0]][_e[1]]return [self.pos[i][0],_e[0],_e[2]+_re[2],_re[2]]def edges(self):m=len(self.pos)result=[]for i in range(m):a,b,c,d=self.get_edge(i)result.append({"from":a,"to":b,"cap":c,"flow":d})return resultdef change_edge(self,i,new_cap,new_flow):m=len(self.pos)assert 0<=i and i<massert 0<=new_flow and new_flow<=new_cap_e=self.g[self.pos[i][0]][self.pos[i][1]]_re=self.g[_e[0]][_e[1]]_e[2]=new_cap-new_flow_re[2]=new_flowdef flow(self,s,t,flow_limit=(1<<63)-1):assert 0<=s and s<self.nassert 0<=t and t<self.nassert s!=tdef bfs():level=[-1 for i in range(self.n)]level[s]=0que=deque([])que.append(s)while(que):v=que.popleft()for to,rev,cap in self.g[v]:if cap==0 or level[to]>=0:continuelevel[to]=level[v]+1if to==t:return levelque.append(to)return leveldef dfs(v,up):if (v==s):return upres=0level_v=level[v]for i in range(Iter[v],len(self.g[v])):Iter[v]=ito,rev,cap=self.g[v][i]if (level_v<=level[to] or self.g[to][rev][2]==0):continued=dfs(to,min(up-res,self.g[to][rev][2]))if d<=0:continueself.g[v][i][2]+=dself.g[to][rev][2]-=dres+=dif res==up:return reslevel[v]=self.nreturn resflow=0while(flow<flow_limit):level=bfs()if level[t]==-1:breakIter=[0 for i in range(self.n)]f=dfs(t,flow_limit-flow)if not(f):breakflow+=freturn flowdef min_cut(self,s):visited=[False for i in range(self.n)]que=deque([])que.append(s)while(len(que)>0):p=que.popleft()visited[p]=Truefor to,rev,cap in self.g[p]:if cap and not(visited[to]):visited[to]=Trueque.append(to)return visitedW = int(input())N = int(input())J = list(map(int,input().split()))M = int(input())C = list(map(int,input().split()))g = mf_graph(102)for i in range(1,N+1):g.add_edge(0,i,J[i-1])for i in range(M):_,*X = map(int,input().split())X = set(X)for j in range(1,N+1):if not j in X:g.add_edge(j,i+51,C[i])for i in range(1,M+1):g.add_edge(50+i,101,C[i-1])ans=g.flow(0,101)if ans>=W:print('SHIROBAKO')else:print('BANSAKUTSUKITA')