結果

問題 No.2713 Just Solitaire
ユーザー navel_tosnavel_tos
提出日時 2024-03-31 17:14:32
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,601 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 77,756 KB
最終ジャッジ日時 2024-03-31 17:14:36
合計ジャッジ時間 3,370 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,608 KB
testcase_01 AC 44 ms
55,608 KB
testcase_02 AC 44 ms
55,608 KB
testcase_03 AC 45 ms
55,608 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 AC 90 ms
77,464 KB
testcase_07 RE -
testcase_08 AC 44 ms
55,608 KB
testcase_09 RE -
testcase_10 RE -
testcase_11 AC 55 ms
63,652 KB
testcase_12 AC 48 ms
61,148 KB
testcase_13 AC 77 ms
74,332 KB
testcase_14 AC 62 ms
68,496 KB
testcase_15 RE -
testcase_16 AC 44 ms
55,608 KB
testcase_17 RE -
testcase_18 RE -
testcase_19 AC 73 ms
73,280 KB
testcase_20 AC 43 ms
55,608 KB
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 WA -
testcase_25 AC 85 ms
77,384 KB
testcase_26 AC 70 ms
72,632 KB
testcase_27 AC 91 ms
77,500 KB
testcase_28 WA -
testcase_29 AC 84 ms
77,624 KB
testcase_30 AC 84 ms
77,360 KB
testcase_31 AC 76 ms
73,776 KB
testcase_32 AC 89 ms
77,616 KB
testcase_33 AC 94 ms
77,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#MMA Contest 018 H

#最大流(stack DFS)
from collections import deque                    # 最大流  V: 頂点数
import sys; sys.setrecursionlimit(10**7)         # 燃やす埋めるにも対応
class maxflow:                                   #  S → A →  
    def __init__(self,V):                        #  ↓   ↓  ↓
        self.V=V                                 #    → B → G
        self.G=[[] for _ in range(V)]            # で、Sが残す頂点とする。このとき、
                                                 # Aを切るならBも切る、は A→B(inf)でOK
    def add_edge(self,u,v,c):                    #
        self.G[u].append([v,c,len(self.G[v])  ]) # Gには [移動先の頂点, 容量, 逆辺の位置] 
        self.G[v].append([u,0,len(self.G[u])-1]) # G[u][辺番号] でアクセス可。逆辺は容量0
                                                 #
    def BFS(self,s):                             #
        D=[-1]*self.V; D[s]=0; Q=deque([s])      #
        while Q:                                 #
            now=Q.popleft()                      #
            for nxt,cap,_ in self.G[now]:        # 容量が残っている辺のみを有効辺とする
                if cap>0 and D[nxt]<0:           #
                    D[nxt]=D[now]+1              #
                    Q.append(nxt)                #
        return D                                 #

    def stackDFS(self,start,fin,total,removed,D):# この頂点以遠の最大流量を考える
        flow=0; Q=[(start,total,False)]          # stack DFS: 再帰の代わりにstackを使う
        while Q:                                 #
            v,tf,back=Q.pop()                    # removed[v]: 頂点vの削除した辺数
            if v==fin: flow=tf; continue         # ゴールした場合はmax flowを流す
            if back and flow:                    # 入りがけか出がけかは変数backで管理
                nxt,_,rev=self.G[v][removed[v]]  #
                self.G[v][removed[v]][1]-=flow   # このDFSでゴールに到達した場合
                self.G[nxt][rev][1]+=flow        # 変数flowがTrueとなり、この流量を流す
                continue                         #
            if back: removed[v]+=1               # 逆にゴールできなかった場合は辺を削除
            while removed[v]<len(self.G[v]):     # なので1回のDFSごとに1個の辺が削除される
                nxt,cap,rev=self.G[v][removed[v]]#
                if cap>0 and D[v]<D[nxt]:        #
                    Q.append((v,tf,1))           #
                    Q.append((nxt,min(tf,cap),0))#
                    break                        #
                else: removed[v]+=1              #
        return flow                              #
                                                 #
    def Calc_max(self,s,fin):                    #
        flow=0                                   #
        while True:                              # 操作1: BFSで辺を引き直す
            D=self.BFS(s)                        # 配列Dは毎回作り直す
            if D[fin]<0: return flow             # これ以上流せなくなった場合は解を出力
            removed=[0]*self.V                   # removed配列はBFSするたびに作り直す
            while True:                          # 操作2: DFSで最短距離のフローを流す
                f=self.stackDFS(s,fin,10**18,removed,D)
                if f==0: break                   # 最短距離でフローが流せなくなったらbreak
                flow+=f                          # 操作1に戻り反復 お疲れ様でした



#入力受取
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

#N + M + 2頂点の頂点を用意
#Sを不採用  Gを採用側として最小カットに帰着する
MF = maxflow(N + M + 2)
S, G = N + M, N + M + 1

#1. カードiを採用すると罰金A[i]円
for i in range(N):
    MF.add_edge(i, G, A[i])
    
#2. 先にsum(B)円もらっておくが、i種類目のボーナスを使わないと罰金B[i]円
for i in range(M):
    _, *C = map(lambda x: int(x) - 1, input().split())
    MF.add_edge(S, M + i, B[i])

    #3. i種類目のボーナスを使うなら、必ずCのボーナスも使う側に回す
    #   S → A, B → G でAをSから切るならBも切る、は A→B(inf)でOK
    for j in C:
        MF.add_edge(i + M, j, 10 ** 18)

#罰金の最小カットを求める
print( sum(B) - MF.Calc_max(S, G) )
0