結果

問題 No.1984 [Cherry 4th Tune *] Dilemma
コンテスト
ユーザー 👑 Kazun
提出日時 2022-03-17 16:15:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 13,373 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 78,336 KB
最終ジャッジ日時 2024-11-08 13:56:48
合計ジャッジ時間 11,617 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 68
権限があれば一括ダウンロードができます

ソースコード

diff # 

#Thansk for aaaaaaaaaa2230
#URL: https://atcoder.jp/contests/practice2/submissions/17017372

from collections import deque
class MaxFlow:
    inf = float("inf")

    class Arc:
        def __init__(self, to, cap, base, direction):
            self.to = to
            self.cap = cap
            self.base = base
            self.rev = None
            self.direction=direction

        def __repr__(self):
            if self.direction==1:
                return "[Source] (To: {}) {} / {}".format(self.to, self.cap,self.base)
            else:
                return "[Target] (From: {}) {} / {}".format(self.to, self.cap,self.base)

    def __init__(self, N):
        """ N 頂点のフロー場を生成する.
        """

        self.N=N
        self.arc = [[] for _ in range(N)]

    def add_arc(self, v, w, cap):
        """ 容量 cap の有向辺 v → w を加える.
        """

        a= self.Arc(w,cap,cap,1)
        a2 = self.Arc(v,0,cap,-1)
        a.rev = a2
        a2.rev = a
        self.arc[v].append(a)
        self.arc[w].append(a2)

    def add_edge(self, v, w, cap):
        """ 容量 cap の無向辺 v → w を加える."""
        self.add_arc(v,w,cap)
        self.add_arc(w,v,cap)

    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 a in self.arc[now]:
                if a.cap and level[a.to]> lw:
                    level[a.to] = lw
                    if a.to == t:
                        return True
                    q.append(a.to)
        return False

    def __dfs(self, s, t, up):
        arc = self.arc
        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:
                    a = arc[w][it[w]].rev
                    flow = min(flow, a.cap)
                for w in st:
                    a = arc[w][it[w]]
                    a.cap += flow
                    a.rev.cap -= flow
                return flow
            lv = level[v]-1
            while it[v] < len(arc[v]):
                a = arc[v][it[v]]
                ra = a.rev
                if ra.cap == 0 or lv != level[a.to]:
                    it[v] += 1
                    continue
                st.append(a.to)
                break
            if it[v] == len(arc[v]):
                st.pop()
                level[v] = self.N
        return 0

    def max_flow(self, source, target, flow_limit=inf):
        """ 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
        return flow

    def flow(self):
        """ 現在の フロー場に流れている各辺の流量を求める.

        """

        F=[{} for _ in range(self.N)]
        arc=self.arc
        for v in range(self.N):
            for a in arc[v]:
                if a.direction==1:
                    F[v][a.to]=a.base-a.cap
        return F

    def min_cut(self,s):
        """ s を 0 に含める最小カットを求める.
        """

        group = [1]*self.N
        Q = deque([s])
        while Q:
            v = Q.pop()
            group[v] = 0
            for a in self.arc[v]:
                if a.cap and group[a.to]:
                    Q.append(a.to)
        return group

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_arc(self.source,i,0)
            F.add_arc(i,self.target,0)

            if self.indivi[i][0]>=0:
                base+=self.indivi[i][0]
                F.add_arc(self.source,i,self.indivi[i][0])
            else:
                F.add_arc(i,self.target,-self.indivi[i][0])

            if self.indivi[i][1]>=0:
                base+=self.indivi[i][1]
                F.add_arc(i,self.target,self.indivi[i][1])
            else:
                F.add_arc(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_arc(self.source,i,-self.indivi[i][0])
            if self.indivi[i][1]!=None:
                F.add_arc(i,self.target,-self.indivi[i][1])

        for x,y,c in self.mutual:
            F.add_arc(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]

#==================================================
#Thansk for aaaaaaaaaa2230
#URL: https://atcoder.jp/contests/practice2/submissions/17017372

from collections import deque
class MaxFlow:
    inf = float("inf")

    class Arc:
        def __init__(self, to, cap, base, direction):
            self.to = to
            self.cap = cap
            self.base = base
            self.rev = None
            self.direction=direction

        def __repr__(self):
            if self.direction==1:
                return "[Source] (To: {}) {} / {}".format(self.to, self.cap,self.base)
            else:
                return "[Target] (From: {}) {} / {}".format(self.to, self.cap,self.base)

    def __init__(self, N):
        """ N 頂点のフロー場を生成する.
        """

        self.N=N
        self.arc = [[] for _ in range(N)]

    def add_arc(self, v, w, cap):
        """ 容量 cap の有向辺 v → w を加える.
        """

        a= self.Arc(w,cap,cap,1)
        a2 = self.Arc(v,0,cap,-1)
        a.rev = a2
        a2.rev = a
        self.arc[v].append(a)
        self.arc[w].append(a2)

    def add_edge(self, v, w, cap):
        """ 容量 cap の無向辺 v → w を加える."""
        self.add_arc(v,w,cap)
        self.add_arc(w,v,cap)

    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 a in self.arc[now]:
                if a.cap and level[a.to]> lw:
                    level[a.to] = lw
                    if a.to == t:
                        return True
                    q.append(a.to)
        return False

    def __dfs(self, s, t, up):
        arc = self.arc
        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:
                    a = arc[w][it[w]].rev
                    flow = min(flow, a.cap)
                for w in st:
                    a = arc[w][it[w]]
                    a.cap += flow
                    a.rev.cap -= flow
                return flow
            lv = level[v]-1
            while it[v] < len(arc[v]):
                a = arc[v][it[v]]
                ra = a.rev
                if ra.cap == 0 or lv != level[a.to]:
                    it[v] += 1
                    continue
                st.append(a.to)
                break
            if it[v] == len(arc[v]):
                st.pop()
                level[v] = self.N
        return 0

    def max_flow(self, source, target, flow_limit=inf):
        """ 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
        return flow

    def flow(self):
        """ 現在の フロー場に流れている各辺の流量を求める.

        """

        F=[{} for _ in range(self.N)]
        arc=self.arc
        for v in range(self.N):
            for a in arc[v]:
                if a.direction==1:
                    F[v][a.to]=a.base-a.cap
        return F

    def min_cut(self,s):
        """ s を 0 に含める最小カットを求める.
        """

        group = [1]*self.N
        Q = deque([s])
        while Q:
            v = Q.pop()
            group[v] = 0
            for a in self.arc[v]:
                if a.cap and group[a.to]:
                    Q.append(a.to)
        return group

#==================================================
N,M,K,P=map(int,input().split())
E=["*"]+list(map(int,input().split()))
F=["*"]+list(map(int,input().split()))
V=["*"]+list(map(int,input().split()))

L=[0]*(N+1)
A=[[] for _ in range(N+1)]
for i in range(1,N+1):
    L[i],*A[i]=list(map(int,input().split()))

I=[0]*(P+1); J=[0]*(P+1)
for p in range(1,P+1):
    I[p],J[p]=map(int,input().split())

#==================================================
H=Project_Selection_Problem(N+M+K+1)

for i in range(1,N+1):
    H.set_one(i,E[i])

    for l in A[i]:
        H.set_zero_one(N+M+l,i,-inf)

for j in range(1,M+1):
    H.set_zero(N+j,F[j])

for p in range(1,P+1):
    H.set_zero_one(N+J[p],I[p],-inf)

for k in range(1,K+1):
    H.set_one(N+M+k,-V[k])

#==================================================
C,R=H.solve(1)
X,Y,Z=R[1:N+1], R[N+1:N+M+1], R[N+M+1:N+M+K+1]
Y=[1-y for y in Y]

X=[0]+X; Y=[0]+Y; Z=[0]+Z

#==================================================
print(C)
print(sum(X)+sum(Y)+sum(Z))

for k in range(1,K+1):
    if Z[k]==1:
        print("Preparation",k)

for i in range(1,N+1):
    if X[i]==1:
        print("Goal",i)

for j in range(1,M+1):
    if Y[j]==1:
        print("Action",j)
0