結果
| 問題 |
No.3201 Corporate Synergy
|
| ユーザー |
👑  Kazun
|
| 提出日時 | 2025-07-11 23:10:58 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 95 ms / 2,000 ms |
| コード長 | 14,862 bytes |
| コンパイル時間 | 220 ms |
| コンパイル使用メモリ | 81,912 KB |
| 実行使用メモリ | 77,420 KB |
| 最終ジャッジ日時 | 2025-07-11 23:11:01 |
| 合計ジャッジ時間 | 2,534 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
#Thansk for aaaaaaaaaa2230
#URL: https://atcoder.jp/contests/practice2/submissions/17017372
from collections import deque
class Arc:
def __init__(self, source: int, target: int, cap: int, base: int, direction: int, id: int):
self.source = source
self.target = target
self.cap = cap
self.base = base
self.rev: Arc = None
self.direction = direction # 1 が順, -1 が逆順
self.id = id
def __repr__(self):
return f"{self.__class__.__name__}(source={self.source}, target={self.target}, cap={self.cap}, base={self.base}, direction={self.direction}, id={self.id})"
class Max_Flow:
inf = float("inf")
def __init__(self, N: int = 0):
""" N 頂点の最大フローを用意する.
Args:
N (int, optional): 位数. Defaults to 0.
"""
self.arc: list[list[Arc]] = [[] for _ in range(N)]
self.__arc_list: list[Arc] =[]
@property
def order(self) -> int:
""" 位数
Returns:
int: 位数
"""
return len(self.arc)
@property
def vertex_count(self) -> int:
""" 頂点数
Returns:
int: 頂点数
"""
return len(self.arc)
@property
def size(self) -> int:
""" サイズ
Returns:
int: サイズ
"""
return len(self.__arc_list)
@property
def arc_count(self):
""" 弧の数
Returns:
int: 弧の数
"""
return len(self.__arc_list)
def add_vertex(self) -> int:
""" 頂点を 1 個追加する.
Returns:
int: 追加した頂点の番号
"""
self.arc.append([])
return self.vertex_count - 1
def add_vertices(self, k: int) -> int:
""" 頂点を k 個追加する.
Args:
k (int): 追加する頂点の数
Returns:
int: 追加する k 個の頂点の番号からなるリスト
"""
n = self.vertex_count
self.arc.extend([[] for _ in range(k)])
return list(range(n, n + k))
def add_arc(self, v: int, w: int, cap: int) -> int:
""" 容量 cap の弧 v → w を追加する.
Args:
v (int): 始点
w (int): 終点
cap (int): 容量
Returns:
int: 追加した弧の番号
"""
m = self.size
arc = Arc(v, w, cap, cap, 1, m)
arc_rev = Arc(w, v, 0, cap, -1, m)
arc.rev = arc_rev
arc_rev.rev = arc
self.arc[v].append(arc)
self.arc[w].append(arc_rev)
self.__arc_list.append(arc)
return m
def get_arc(self, i: int) -> Arc:
""" i 番目の弧を得る.
Args:
i (int): 弧の番号
Returns:
Arc: 弧
"""
assert 0 <= i < self.size
return self.__arc_list[i]
def get_all_arcs(self) -> list[Arc]:
return [self.get_arc(i) for i in range(self.size)]
def change_arc(self, i, new_cap, new_flow):
""" i 番目の辺の情報を変更する.
"""
assert 0 <= i < self.size
assert 0 <= new_flow<=new_cap
a=self.__arc_list[i]
a.base=new_cap; a.cap=new_cap-new_flow
a.rev.base=new_cap; a.rev.cap=new_flow
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: int, t: int) -> bool:
level = self.level = [-1] * self.vertex_count
Q = deque([s])
level[s] = 0
while Q:
v = Q.popleft()
next_level = level[v] + 1
for arc in self.arc[v]:
if not(arc.cap and level[arc.target] == -1):
continue
level[arc.target] = next_level
if arc.target == t:
return True
Q.append(arc.target)
return False
def __dfs(self, s: int, t: int, up: int) -> int:
arc_to = self.arc
it = self.it
level = self.level
st = deque([t])
while st:
v = st[-1]
if v == s:
break
lv = level[v]-1
while it[v] < len(arc_to[v]):
arc_rev = arc_to[v][it[v]]
arc = arc_rev.rev
if arc.cap == 0 or lv != level[arc.source]:
it[v] += 1
continue
st.append(arc.source)
break
if it[v] == len(arc_to[v]):
st.pop()
level[v] = -1
else:
return 0
st.pop()
flow = up
for w in st:
arc = arc_to[w][it[w]].rev
flow = min(flow, arc.cap)
for w in st:
arc_rev = arc_to[w][it[w]]
arc_rev.cap += flow
arc_rev.rev.cap -= flow
return flow
def max_flow(self, source: int, target: int, flow_limit: int = inf) -> int:
""" source から target へ flow_limit を上限として流せるだけ流したときの "追加で発生する" 流量を求める.
Args:
source (int): 始点
target (int): 終点
flow_limit (int, optional): 流量の上限. Defaults to inf.
Returns:
int: "追加で発生する" 流量
"""
flow = 0
while flow < flow_limit and self.__bfs(source, target):
self.it = [0] * self.vertex_count
while flow < flow_limit:
f = self.__dfs(source, target, flow_limit - flow)
if f == 0:
break
flow += f
return flow
def get_flow(self) -> list[list[tuple[int, int, int]]]:
F = [[] for _ in range(self.vertex_count)]
for arc in self.__arc_list:
F[arc.source].append((arc.id, arc.target, arc.base - arc.cap))
return F
def min_cut(self, s: int) -> list[int]:
""" s を 0 側に含める最小カットを求める.
Args:
s (int): 頂点番号
Returns:
list[int]: 0, 1 からなる長さが位数のリスト. 最小カットは 0 側と 1 側に分かれる. 頂点 s は必ず 0 側になる.
"""
group = [1] * self.vertex_count
Q = deque([s])
while Q:
v = Q.pop()
group[v] = 0
for arc in self.arc[v]:
if arc.cap and group[arc.target]:
Q.append(arc.target)
return group
def refresh(self):
for a in self.__arc_list:
a.cap = a.base
a.rev.cap = 0
inf=float("inf")
class Project_Selection_Problem:
def __init__(self, N = 0):
""" N 要素の Project Selection Problem を生成する.
N: int
"""
self.N = N
self.ver_num = N + 2
self.base = 0
self.source = N
self.target = N + 1
self.indivi = [[0, 0] for _ in range(N + 2)]
self.mutual: list[tuple[int, int, int]] = []
def add_vertex(self) -> int:
""" 変数を 1 個追加する.
Returns:
int: 追加した頂点の番号
"""
n = self.ver_num
self.indivi.append([0,0])
self.ver_num += 1
return n
def __add_vertex_inner(self):
n = self.ver_num
self.indivi.append([None, None])
self.ver_num += 1
return n
def add_vertices(self, k: int) -> int:
""" 変数を k 個追加する.
Args:
k (int): 追加する頂点の番号
Returns:
int: 追加した k 個の頂点番号からなるリスト
"""
n = self.ver_num
self.indivi.extend([[0, 0] for _ in range(k)])
self.ver_num += k
return list(range(n, n + k))
def set_zero_one(self, x: int, y: int, a: int):
""" 「h(x) = 0, h(y) = 1 のとき, a (<=0) 点を得る」という観点を追加する.
Args:
x (int): h(x) = 0 を課す変数の番号
y (int): h(y) = 1 を課す変数の番号
a (int): 観点の得点 (負でなくてはならない)
"""
assert 0 <= x < self.N
assert 0 <= y < self.N
assert a <= 0, f"a は負でなくてはなりません (a = {a})"
self.mutual.append((x, y, -a))
def set_zero(self, x: int, a: int):
""" 「h(x) = 0 のとき, a 点を得る」という観点を追加する.
Args:
x (int): h(x) = 0 を課す変数の番号
a (int): 観点の得点
"""
assert 0 <= x < self.N
self.indivi[x][0] += a
def set_one(self, x: int, a: int):
""" 「h(x) = 1 のとき, a 点を得る」という観点を追加する.
Args:
x (int): h(x) = 1 を課す変数の番号
a (int): 観点の得点
"""
assert 0 <= x < self.N
self.indivi[x][1] += a
def set_all_zero(self, X: list[int], a: int):
""" 「h(x) = 0 (forall x in X) のとき, a (>= 0) 点を得る」という観点を追加する.
Args:
X (list[int]): 変数の番号のリスト
a (int): 観点の得点 (正でなくてはならない)
"""
assert a >= 0, f"a は正でなくてはなりません (a = {a})"
k = self.__add_vertex_inner()
self.base += a
self.indivi[k][0] = -a
for x in X:
assert 0 <= x < self.N
self.mutual.append((k, x, inf))
def set_all_one(self, X: list[int], a: int):
""" 「h(x) = 1 (forall x in X) のとき, a (>= 0) 点を得る」という観点を追加する.
Args:
X (list[int]): 変数の番号のリスト
a (int): 観点の得点 (正でなくてはならない)
"""
assert a >= 0, f"a は正でなくてはなりません (a = {a})"
k = self.__add_vertex_inner()
self.base += a
self.indivi[k][1] = -a
for x in X:
assert 0 <= x < self.N
self.mutual.append((x, k, inf))
def set_not_equal(self, x:int, y: int, a: int):
""" 「h(x) != h(y) のとき, a (<= 0) 点を得る」という観点を追加する.
Args:
x (int):
y (int):
a (int): 観点の得点 (負でなくてはならない)
"""
assert 0 <= x < self.N
assert 0 <= y < self.N
assert a <= 0, f"a は負でなくてはなりません (a = {a})"
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) 点を得る」という観点を追加する.
Args:
x (int):
y (int):
a (int): 観点の得点 (正でなくてはならない)
"""
assert 0 <= x < self.N
assert 0 <= y < self.N
assert a >= 0, f"a は負でなくてはなりません (a = {a})"
self.set_all_zero([x, y], a)
self.set_all_one([x, y], a)
def ban_zero(self, x: int):
""" h(x) = 0 となることを禁止する (実行したら -inf 点になる)
Args:
x (int): h(x) = 0 を禁止する変数の番号
"""
assert 0 <= x < self.N
self.set_zero(x, -inf)
def ban_one(self, x: int):
""" h(x) = 1 となることを禁止する (実行したら -inf 点になる).
Args:
x (int): h(x) = 1 を禁止する変数の番号
"""
assert 0 <= x < self.N
self.set_one(x, -inf)
def force_zero(self, x: int):
""" h(x) = 0 を絶対条件にする (要するに, ban_one(x)).
Args:
x (int): h(x) = 0 を指定する変数の番号
"""
assert 0 <= x < self.N
self.ban_one(x)
def force_one(self, x: int):
""" h(x) = 1 を絶対条件にする (要するに, ban_zero(x)).
Args:
x (int): h(x) = 1 を指定する変数の番号
"""
assert 0 <= x < self.N
self.ban_zero(x)
def increase(self, X: list[int]):
""" h(x[0]) <= h(x[1]) <= ... <= h(x[k-1]) (h(x[i]) = 1, h(x[i+1]) = 0 を禁止) という条件を追加する.
Args:
X (list[int]): 単調性を課す変数の番号のリスト
"""
for i in range(len(X) - 1):
self.set_zero_one(X[i + 1], X[i], -inf)
def decrease(self, X: list[int]):
""" h(x[0]) >= h(x[1]) >= ... >= h(x[k-1]) (h(x[i]) = 0, h(x[i+1]) = 1 を禁止) という条件を追加する.
Args:
X (list[int]): 単調性を課す変数の番号のリスト
"""
self.increase(X[::-1])
def solve(self):
""" Project Selection Problem を解く. """
F = Max_Flow(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] is not None:
F.add_arc(self.source, i, -self.indivi[i][0])
if self.indivi[i][1] is not 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)
self.__ans = base - alpha
self.__choice = F.min_cut(self.source)
@property
def ans(self):
return self.__ans
@property
def choice(self):
return self.__choice
#==================================================
def solve():
N = int(input())
F = Project_Selection_Problem(N + 1)
P = [0] + list(map(int, input().split()))
for i in range(1, N + 1):
F.set_one(i, P[i])
M = int(input())
inf = pow(10, 18)
for _ in range(M):
u, v = map(int, input().split())
F.set_zero_one(u, v, -inf)
K = int(input())
for _ in range(K):
a, b, s = map(int, input().split())
F.set_all_one([a, b], s)
F.solve()
return F.ans
#==================================================
print(solve())