結果
| 問題 | No.957 植林 |
| コンテスト | |
| ユーザー |
 Kazun
|
| 提出日時 | 2021-08-26 02:03:25 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,918 bytes |
| 記録 | |
| コンパイル時間 | 156 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 637,440 KB |
| 最終ジャッジ日時 | 2024-11-17 11:03:06 |
| 合計ジャッジ時間 | 96,583 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 TLE * 25 MLE * 8 |
ソースコード
#Thansk for aaaaaaaaaa2230
#URL:https://atcoder.jp/contests/practice2/submissions/17017319
import sys
from collections import deque
class MaxFlow:
class Edge:
def __init__(self,target,cap,base,direct):
self.target = target
self.cap = cap
self.flow=0
self.base=base
self.direct=direct
self.rev = None
def __str__(self):
if self.direct==1:
return "[S](target:{}, flow/cap:{}/{})".format(self.target,self.flow,self.base)
else:
return "[T](source:{}, flow/cap:{}/{})".format(self.target,self.flow,self.base)
__repr__=__str__
def __init__(self,N):
""" N 頂点からなる Flow 場を生成する.
"""
self.N = N
self.graph = [[] for _ in range(N)]
self.old_flow=0
def add_edge(self,u,v, cap):
""" 容量が cap である有向辺 u→v を加える.
u,v: 頂点
cap: 容量
"""
graph = self.graph
edge = self.Edge(v,cap,cap,1)
edge2 = self.Edge(u,0,cap,-1)
edge.rev = edge2
edge2.rev = edge
graph[u].append(edge)
graph[v].append(edge2)
def __bfs(self, s, t):
level = self.level = [self.N]*self.N
q = deque([s])
level[s] = 0
while q:
now = q.popleft()
lw = level[now]+1
for e in self.graph[now]:
if e.cap and level[e.target]> lw:
level[e.target] = lw
if e.target == t:
return True
q.append(e.target)
return False
def __dfs(self, s, t, up):
graph = self.graph
it = self.it
level = self.level
st = deque([t])
while st:
v = st[-1]
if v == s:
st.pop()
flow = up
for w in st:
e = graph[w][it[w]].rev
flow = min(flow, e.cap)
for w in st:
e = graph[w][it[w]]
e.cap += flow
e.flow-=flow
e.rev.cap -= flow
e.rev.flow+=flow
return flow
lv = level[v]-1
while it[v] < len(graph[v]):
e = graph[v][it[v]]
re = e.rev
if re.cap == 0 or lv != level[e.target]:
it[v] += 1
continue
st.append(e.target)
break
if it[v] == len(graph[v]):
st.pop()
level[v] = self.N
return 0
def max_flow(self,source,target,flow_limit=float("inf")):
""" source から target に流す最大流の大きさを出力する.
source, target: 頂点
flow_limit: "追加で流す" 最大流の上限
"""
Flow=0
while Flow < flow_limit and self.__bfs(source,target):
self.it=[0]*self.N
while Flow<flow_limit:
F=self.__dfs(source,target,flow_limit-Flow)
if F==0:break
Flow+=F
self.old_flow+=Flow
return self.old_flow
def flow(self):
""" 現在の flow の状況を求める.
[Output]
辞書 D が返る. D[u][v] で 有効辺 u→v に流れる量を表す.
"""
X=[{} for _ in range(self.N)]
for i in range(self.N):
x=X[i]
for e in self.graph[i]:
if e.direct==-1: continue
if e.target not in x: x[e.target]=0
x[e.target]+=e.flow
return X
def min_cut(self,s):
""" sにおける最小カットを求める.
[Input]
s: sorce (s が 0 側になる)
[Output]
0 or 1 のリストで, 0同士と1同士で分ける.
"""
visited = [1]*self.N
q = deque([s]); visited[s]=0
while q:
v = q.pop()
for e in self.graph[v]:
if e.cap and visited[e.target]==1:
visited[e.target]=0
q.append(e.target)
return visited
inf=float("inf")
class Project_Selection_Problem:
def __init__(self,N):
""" N 要素の Project Selection Problem を生成する.
N:int
"""
self.N=N
self.ver_num=N+2
self.source=N
self.base=0
self.target=N+1
self.indivi=[[0,0] for _ in range(N+2)]
self.mutual=[]
def set_zero_one(self,x,y,a):
""" h(x)=0, h(y)=1 のとき, a (<=0) 点を得るという条件を追加する.
0<=x,y<N
a<=0
"""
assert 0<=x<self.N
assert 0<=y<self.N
assert a<=0
self.mutual.append((x,y,-a))
def set_zero(self,x,a):
""" h(x)=0 のとき, a 点を得るという条件を追加する.
0<=x<N
"""
assert 0<=x<self.N
self.indivi[x][0]+=a
def set_one(self,x,a):
""" h(x)=1 のとき, a 点を得るという条件を追加する.
0<=x<N
"""
assert 0<=x<self.N
self.indivi[x][1]+=a
def set_all_zero(self,X,a):
""" h(x)=0 (forall x in X) のとき, a (>=0) 点を得るという条件を追加する.
0<=x<N
a>=0
"""
assert a>=0
self.indivi.append([None,None])
self.ver_num+=1
self.base+=a
self.indivi[-1][0]=-a
for x in X:
assert 0<=x<self.N
self.mutual.append((self.ver_num-1,x,inf))
def set_all_one(self,X,a):
""" h(x)=1 (forall x in X) のとき, a (>=0) 点を得るという条件を追加する.
0<=x<N
a>=0
"""
assert a>=0
self.indivi.append([None,None])
self.ver_num+=1
self.base+=a
self.indivi[-1][1]=-a
for x in X:
assert 0<=x<self.N
self.mutual.append((x,self.ver_num-1,inf))
def set_not_equal(self,x,y,a):
""" h(x)!=h(y) ならば, a (<=0) 点を得るという条件を追加する.
0<=x,y<N
a<=0
"""
assert 0<=x<self.N and 0<=y<self.N
assert a<=0
self.set_zero_one(x,y,a)
self.set_zero_one(y,x,a)
def set_equal(self,x,y,a):
""" h(x)=h(y) ならば, a (>=0) 点を得るという条件を追加する.
0<=x,y<N
a>=0
"""
assert 0<=x<self.N and 0<=y<self.N
assert a>=0
self.set_all_zero([x,y],a)
self.set_all_one([x,y],a)
def ban_zero(self,x):
""" h(x)=0 となることを禁止する. (実行したら -inf 点になる)
0<=x<N
"""
assert 0<=x<self.N
self.set_zero(x,-inf)
def ban_one(self,x):
""" h(x)=1 となることを禁止する. (実行したら -inf 点になる)
0<=x<N
"""
assert 0<=x<self.N
self.set_one(x,-inf)
def solve(self,Mode=0):
""" Project Selection Problem を解く.
Mode
0: 最大値のみ
1: 最大値とそれを達成する例
"""
F=MaxFlow(self.ver_num)
base=self.base
for i in range(self.N):
F.add_edge(self.source,i,0)
F.add_edge(i,self.target,0)
if self.indivi[i][0]>=0:
base+=self.indivi[i][0]
F.add_edge(self.source,i,self.indivi[i][0])
else:
F.add_edge(i,self.target,-self.indivi[i][0])
if self.indivi[i][1]>=0:
base+=self.indivi[i][1]
F.add_edge(i,self.target,self.indivi[i][1])
else:
F.add_edge(self.source,i,-self.indivi[i][1])
for i in range(self.target+1,self.ver_num):
if self.indivi[i][0]!=None:
F.add_edge(self.source,i,-self.indivi[i][0])
if self.indivi[i][1]!=None:
F.add_edge(i,self.target,-self.indivi[i][1])
for x,y,c in self.mutual:
F.add_edge(x,y,c)
alpha=F.max_flow(self.source,self.target)
if Mode==0:
return base-alpha
else:
return base-alpha,F.min_cut(self.source)[:self.N]
#==================================================
def f(i,j):
return i*W+j
#==================================================
H,W=map(int,input().split())
G=[]
for _ in range(H):
G.append(list(map(int,input().split())))
R=list(map(int,input().split()))
C=list(map(int,input().split()))
P=Project_Selection_Problem(H*W)
for i in range(H):
for j in range(W):
P.set_one(f(i,j),-G[i][j])
for i in range(H):
P.set_all_one(range(i*W,(i+1)*W),R[i])
for j in range(W):
P.set_all_one(range(j,H*W,W),C[j])
print(P.solve(0))