結果

問題 No.957 植林
ユーザー 👑 KazunKazun
提出日時 2021-08-26 02:11:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 8,928 bytes
コンパイル時間 236 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 416,912 KB
最終ジャッジ日時 2024-11-17 11:12:45
合計ジャッジ時間 86,158 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
60,416 KB
testcase_01 AC 49 ms
271,900 KB
testcase_02 AC 49 ms
60,544 KB
testcase_03 AC 1,315 ms
410,932 KB
testcase_04 AC 1,386 ms
189,956 KB
testcase_05 AC 1,105 ms
416,912 KB
testcase_06 AC 1,722 ms
209,628 KB
testcase_07 AC 1,513 ms
188,948 KB
testcase_08 AC 566 ms
188,384 KB
testcase_09 AC 564 ms
410,024 KB
testcase_10 AC 612 ms
194,424 KB
testcase_11 AC 582 ms
413,944 KB
testcase_12 AC 575 ms
187,260 KB
testcase_13 AC 485 ms
403,756 KB
testcase_14 AC 533 ms
195,764 KB
testcase_15 AC 514 ms
416,084 KB
testcase_16 AC 467 ms
175,576 KB
testcase_17 AC 467 ms
407,592 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 AC 311 ms
159,288 KB
testcase_42 AC 320 ms
158,224 KB
testcase_43 AC 642 ms
203,040 KB
testcase_44 AC 738 ms
204,304 KB
testcase_45 AC 49 ms
54,784 KB
testcase_46 AC 49 ms
55,168 KB
testcase_47 AC 51 ms
296,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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]
#==================================================
H,W=map(int,input().split())

G=[]
R_sum=[0]*H; C_sum=[0]*W

for i in range(H):
    g=list(map(int,input().split()))
    G.append(g)

    for j in range(W):
        R_sum[i]+=g[j]
        C_sum[j]+=g[j]


R=list(map(int,input().split()))
C=list(map(int,input().split()))

P=Project_Selection_Problem(H+W)

for i in range(H):
    P.set_one(i,R[i]-R_sum[i])

for j in range(W):
    P.set_one(j+H,C[j]-C_sum[j])

for i in range(H):
    for j in range(W):
        P.set_all_one([i,j+H],G[i][j])

print(P.solve(0))
0