結果
| 問題 | No.519 アイドルユニット |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2022-05-21 19:41:46 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 182 ms / 1,000 ms |
| コード長 | 9,994 bytes |
| コンパイル時間 | 151 ms |
| コンパイル使用メモリ | 81,920 KB |
| 実行使用メモリ | 75,904 KB |
| 最終ジャッジ日時 | 2024-09-20 12:07:20 |
| 合計ジャッジ時間 | 3,536 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 53 ms
63,104 KB |
| testcase_01 | AC | 79 ms
75,904 KB |
| testcase_02 | AC | 65 ms
71,168 KB |
| testcase_03 | AC | 60 ms
67,712 KB |
| testcase_04 | AC | 45 ms
56,320 KB |
| testcase_05 | AC | 46 ms
56,192 KB |
| testcase_06 | AC | 46 ms
56,660 KB |
| testcase_07 | AC | 47 ms
56,704 KB |
| testcase_08 | AC | 47 ms
56,960 KB |
| testcase_09 | AC | 52 ms
63,360 KB |
| testcase_10 | AC | 62 ms
66,432 KB |
| testcase_11 | AC | 182 ms
67,200 KB |
| testcase_12 | AC | 45 ms
56,448 KB |
| testcase_13 | AC | 64 ms
68,992 KB |
| testcase_14 | AC | 53 ms
64,384 KB |
| testcase_15 | AC | 63 ms
67,456 KB |
| testcase_16 | AC | 61 ms
67,712 KB |
| testcase_17 | AC | 60 ms
67,968 KB |
| testcase_18 | AC | 65 ms
70,528 KB |
| testcase_19 | AC | 64 ms
66,816 KB |
| testcase_20 | AC | 64 ms
68,096 KB |
| testcase_21 | AC | 62 ms
68,244 KB |
| testcase_22 | AC | 65 ms
69,380 KB |
| testcase_23 | AC | 62 ms
67,584 KB |
| testcase_24 | AC | 62 ms
68,480 KB |
| testcase_25 | AC | 63 ms
70,036 KB |
| testcase_26 | AC | 62 ms
69,376 KB |
| testcase_27 | AC | 64 ms
69,888 KB |
| testcase_28 | AC | 63 ms
69,632 KB |
| testcase_29 | AC | 56 ms
65,280 KB |
| testcase_30 | AC | 66 ms
69,376 KB |
| testcase_31 | AC | 74 ms
74,240 KB |
| testcase_32 | AC | 68 ms
71,424 KB |
| testcase_33 | AC | 47 ms
56,576 KB |
ソースコード
INF = 1 << 60
from collections import deque
class GeneralWeightedMatching():
def __init__(self, n):
self.n = n
self.nx = n
self.m = 2 * n + 1
self.u = [0] * self.m * self.m
self.v = [0] * self.m * self.m
self.w = [0] * self.m * self.m
self.match = [0] * self.m
self.slack = [0] * self.m
self.flower = [[] for _ in range(self.m)]
self.flower_from = [0] * self.m * self.m
self.label = [0] * self.m
self.root = [0] * self.m
self.par = [0] * self.m
self.col = [0] * self.m
self.vis = [0] * self.m
self.que = deque()
self.t = 0
for u in range(1, self.m):
for v in range(1, self.m):
self.u[u * self.m + v] = u
self.v[u * self.m + v] = v
def dist(self, u, v):
u, v = self.u[u * self.m + v], self.v[u * self.m + v]
return self.label[u] + self.label[v] - self.w[u * self.m + v] * 2
def add_edge(self, u, v, w):
u += 1; v += 1
self.w[u * self.m + v] = max(self.w[u * self.m + v], w)
self.w[v * self.m + u] = max(self.w[v * self.m + u], w)
def update_slack(self, u, x):
if not self.slack[x] or self.dist(u, x) < self.dist(self.slack[x], x):
self.slack[x] = u
def set_slack(self, x):
self.slack[x] = 0
for u in range(1, self.n + 1):
if self.w[u * self.m + x] > 0 and self.root[u] != x and self.col[self.root[u]] == 0:
self.update_slack(u, x)
def que_push(self, x):
stack = [x]
while stack:
x = stack.pop()
if x <= self.n:
self.que.append(x)
continue
for i, fi in enumerate(self.flower[x]):
stack.append(fi)
def set_root(self, x, b):
stack = [x]
while stack:
x = stack.pop()
self.root[x] = b
if x <= self.n:
continue
for i, fi in enumerate(self.flower[x]):
stack.append(fi)
def get_pr(self, b, xr):
f = self.flower[b]
pr = f.index(xr)
if pr % 2 == 1:
f = self.flower[b] = f[0:1] + f[1:][::-1]
return len(f) - pr
else:
return pr
def set_match(self, u, v):
self.match[u] = self.v[u * self.m + v]
if u <= self.n:
return
xr = self.flower_from[u * self.m + self.u[u * self.m + v]]
pr = self.get_pr(u, xr)
f = self.flower[u]
for i in range(pr):
self.set_match(f[i], f[i ^ 1])
self.set_match(xr, v)
self.flower[u] = f[pr:] + f[:pr]
def augment(self, u, v):
xnv = self.root[self.match[u]]
self.set_match(u, v)
while xnv:
self.set_match(xnv, self.root[self.par[xnv]])
u, v = self.root[self.par[xnv]], xnv
xnv = self.root[self.match[u]]
self.set_match(u, v)
def get_lca(self, u, v):
self.t += 1
while u or v:
if not u:
u, v = v, u
continue
if self.vis[u] == self.t:
return u
self.vis[u] = self.t
u = self.root[self.match[u]]
if u: u = self.root[self.par[u]]
u, v = v, u
return 0
def add_blossom(self, u, lca, v):
b = self.n + 1
while b <= self.nx and self.root[b]:
b += 1
if b > self.nx:
self.nx += 1
self.label[b] = 0
self.col[b] = 0
self.match[b] = self.match[lca]
f = self.flower[b] = []
f.append(lca)
x = u
while x != lca:
f.append(x)
y = self.root[self.match[x]]
f.append(y)
self.que_push(y)
x = self.root[self.par[y]]
f = self.flower[b] = f[0:1] + f[1:][::-1]
x = v
while x != lca:
f.append(x)
y = self.root[self.match[x]]
f.append(y)
self.que_push(y)
x = self.root[self.par[y]]
self.set_root(b, b)
for x in range(1, self.nx + 1):
self.w[b * self.m + x] = self.w[x * self.m + b] = 0
for x in range(1, self.n + 1):
self.flower_from[b * self.m + x] = 0
for i, xs in enumerate(f):
for x in range(1, self.nx + 1):
if self.w[b * self.m + x] == 0 or self.dist(xs, x) < self.dist(b, x):
self.u[b * self.m + x] = self.u[xs * self.m + x]
self.u[x * self.m + b] = self.u[x * self.m + xs]
self.v[b * self.m + x] = self.v[xs * self.m + x]
self.v[x * self.m + b] = self.v[x * self.m + xs]
self.w[b * self.m + x] = self.w[xs * self.m + x]
self.w[x * self.m + b] = self.w[x * self.m + xs]
for x in range(1, self.n + 1):
if self.flower_from[xs * self.m + x]:
self.flower_from[b * self.m + x] = xs
self.set_slack(b)
def expand_blossom(self, b):
f = self.flower[b]
for i, fi in enumerate(f):
self.set_root(fi, fi)
xr = self.flower_from[b * self.m + self.u[b * self.m + self.par[b]]]
pr = self.get_pr(b, xr)
f = self.flower[b]
for i in range(0, pr, 2):
xs = f[i]
xns = f[i + 1]
self.par[xs] = self.u[xns * self.m + xs]
self.col[xs] = 1
self.col[xns] = 0
self.slack[xs] = 0
self.set_slack(xns)
self.que_push(xns)
self.col[xr] = 1
self.par[xr] = self.par[b]
for i in range(pr + 1, len(f)):
xs = f[i]
self.col[xs] = -1
self.set_slack(xs)
self.root[b] = 0
def on_found_edge(self, u, v):
eu = self.u[u * self.m + v]
ev = self.v[u * self.m + v]
u = self.root[eu]
v = self.root[ev]
if self.col[v] == -1:
self.par[v] = eu
self.col[v] = 1
nu = self.root[self.match[v]]
self.slack[v] = self.slack[nu] = 0
self.col[nu] = 0
self.que_push(nu)
elif self.col[v] == 0:
lca = self.get_lca(u, v)
if not lca:
self.augment(u, v)
self.augment(v, u)
return 1
else:
self.add_blossom(u, lca, v)
return 0
def matching(self):
for i in range(self.nx + 1):
self.col[i] = -1
self.slack[i] = 0
self.que.clear()
for x in range(1, self.nx + 1):
if self.root[x] == x and not self.match[x]:
self.par[x] = 0
self.col[x] = 0
self.que_push(x)
if not self.que:
return 0
while True:
while self.que:
u = self.que.popleft()
if self.col[self.root[u]] == 1:
continue
for v in range(1, self.n + 1):
if self.w[u * self.m + v] and self.root[u] != self.root[v]:
if self.dist(u, v) == 0:
if self.on_found_edge(u, v):
return 1
else:
self.update_slack(u, self.root[v])
d = INF
for b in range(self.n + 1, self.nx + 1):
if self.root[b] == b and self.col[b] == 1:
d = min(d, self.label[b] // 2)
for x in range(1, self.nx + 1):
if self.root[x] == x and self.slack[x]:
if self.col[x] == -1:
d = min(d, self.dist(self.slack[x], x))
elif self.col[x] == 0:
d = min(d, self.dist(self.slack[x], x) // 2)
for u in range(1, self.n + 1):
if self.col[self.root[u]] == 0:
if self.label[u] <= d:
return 0
self.label[u] -= d
elif self.col[self.root[u]] == 1:
self.label[u] += d
for b in range(self.n + 1, self.nx + 1):
if self.root[b] == b:
if self.col[b] == 0:
self.label[b] += d * 2
elif self.col[b] == 1:
self.label[b] -= d * 2
self.que.clear()
for x in range(1, self.nx + 1):
if self.root[x] == x and self.slack[x] and self.root[self.slack[x]] != x and self.dist(self.slack[x], x) == 0:
if self.on_found_edge(self.slack[x], x):
return 1
for b in range(self.n + 1, self.nx + 1):
if self.root[b] == b and self.col[b] == 1 and self.label[b] == 0:
self.expand_blossom(b)
return 0
def solve(self):
cnt = 0
ans = 0
for u in range(self.n + 1):
self.root[u] = u
self.flower[u].clear()
w_max = 0
for u in range(1, self.n + 1):
for v in range(1, self.n + 1):
self.flower_from[u * self.m + v] = u if u == v else 0
w_max = max(w_max, self.w[u * self.m + v])
for u in range(1, self.n + 1):
self.label[u] = w_max
while self.matching():
cnt += 1
for u in range(1, self.n + 1):
if self.match[u] and self.match[u] < u:
ans += self.w[u * self.m + self.match[u]]
for i in range(self.n):
self.match[i] = self.match[i + 1] - 1
return ans, cnt
N = int(input())
F = [list(map(int, input().split())) for _ in range(N)]
G = GeneralWeightedMatching(N)
for i in range(N - 1):
for j in range(i + 1, N):
G.add_edge(i, j, F[i][j])
res, _ = G.solve()
print(res)