結果
問題 | No.2263 Perms |
ユーザー |
![]() |
提出日時 | 2023-04-04 17:03:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 213 ms / 2,000 ms |
コード長 | 3,751 bytes |
コンパイル時間 | 1,052 ms |
コンパイル使用メモリ | 82,088 KB |
実行使用メモリ | 81,860 KB |
最終ジャッジ日時 | 2024-10-01 08:48:46 |
合計ジャッジ時間 | 7,487 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
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((a,b,c,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])):to,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 visitedn,m=map(int,input().split())a=[]for i in range(n):a.append(list(map(int,input().split())))for i in range(n):sm=0for j in range(n):sm+=a[i][j]if sm!=m:exit(print(-1))for j in range(n):sm=0for i in range(n):sm+=a[i][j]if sm!=m:exit(print(-1))for _ in range(m):g=mf_graph(2*n+2)S=2*nT=2*n+1for i in range(n):g.add_edge(S,i,1)g.add_edge(i+n,T,1)for j in range(n):if a[i][j]>0:g.add_edge(i,n+j,1)g.flow(S,T,n)p=[-1]*nfor e in g.edges():frm=e[0]to=e[1]-nflow=e[3]if 0<=frm<n and 0<=to<n and flow==1:p[frm]=toa[frm][to]-=1assert sorted(p)==list(range(n))print(*[i+1 for i in p])