結果
| 問題 |
No.519 アイドルユニット
|
| コンテスト | |
| ユーザー |
 rpy3cpp
|
| 提出日時 | 2017-05-30 23:30:02 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 87 ms / 1,000 ms |
| コード長 | 18,314 bytes |
| コンパイル時間 | 350 ms |
| コンパイル使用メモリ | 82,296 KB |
| 実行使用メモリ | 76,744 KB |
| 最終ジャッジ日時 | 2024-10-03 03:58:17 |
| 合計ジャッジ時間 | 3,334 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 34 |
ソースコード
# 計算量O(n^3)
# NetworkX の max_wieght_matching() のソースをもとに改変。
# 元のソースコードに対し、以下の変更を加えた。
# ・入力するグラフ G は、NetworkXの Graph オブジェクトでなく、下記で定義した簡易版のGraphオブジェクト
# ・返り値は、マッチングのペアを表す辞書 mate でなく、マッチングした辺の合計の最大値 max_weight に変更。
# ・コメントの削除
# ・maxcardinality = True にデフォルトを変更。
# ・検算用の関数 および assert文を削除。
#
# 以下のコピーライト表記は、元のソースコードのもの。
# Copyright (C) 2004-2015 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
# Copyright (C) 2011 by
# Nicholas Mancuso <nick.mancuso@gmail.com>
# All rights reserved.
# BSD license.
from itertools import repeat
class Graph(object):
'''重み付き無向グラフを表すクラス。 max_weight_matching() の入力に使うためのラッパーで、networkXのグラフクラスを模倣する。
G.nodes() : ノードのリストを返す。
G.edges_iter(data=True): (i, j, data)のタプルを順にyieldする。i, j は辺の両端の頂点。dataは、辺に関連付けられたデータ（辞書）。
data.get("weight") で辺の重みを取得できる。 -> 回りくどいので、dataを辞書ではなく、重みを表すintとした。
G[i][j]: 辺(i, j)に関連付けられたデータを返す。->回りくどいので、dataを返すのでなく、重みを表すintを返すとした。
G.neighbors_iter(v): 頂点 v に隣接する頂点を順にyieldする。
'''
def __init__(self, Es):
''' Es: Es[v] に、頂点vの辺の一覧の辞書（隣接頂点をキー、辺の重みを値）を格納したリスト
頂点は、0 から、len(Es)-1 までの整数連番で表す。
'''
self.Vs = list(range(len(Es)))
self.Es = Es
self._init_edges()
def nodes(self):
return self.Vs[:]
def neighbors_iter(self, v):
return self.Es[v].keys()
def edges_iter(self, data=True):
if data:
return iter(self.edges_with_weight)
else:
return iter(self.edges)
def __getitem__(self, v):
return self.Es[v]
def _init_edges(self):
edges = set()
for v in self.Vs:
for u, w in self.Es[v].items():
edges.add((min(v, u), max(v, u), w))
self.edges_with_weight = list(edges)
self.edges = [(u, v) for u, v, w in self.edges_with_weight]
def max_weight_matching(G, maxcardinality=True):
"""Compute a maximum-weighted matching of G.
A matching is a subset of edges in which no node occurs more than once.
The cardinality of a matching is the number of matched edges.
The weight of a matching is the sum of the weights of its edges.
Parameters
----------
G : NetworkX graph
Undirected graph
maxcardinality: bool, optional
If maxcardinality is True, compute the maximum-cardinality matching
with maximum weight among all maximum-cardinality matchings.
Returns
-------
mate : dictionary -> max_weight : int を返す仕様に変更。
The matching is returned as a dictionary, mate, such that
mate[v] == w if node v is matched to node w. Unmatched nodes do not
occur as a key in mate.
Notes
-----
If G has edges with 'weight' attribute the edge data are used as
weight values else the weights are assumed to be 1.
This function takes time O(number_of_nodes ** 3).
If all edge weights are integers, the algorithm uses only integer
computations. If floating point weights are used, the algorithm
could return a slightly suboptimal matching due to numeric
precision errors.
This method is based on the "blossom" method for finding augmenting
paths and the "primal-dual" method for finding a matching of maximum
weight, both methods invented by Jack Edmonds [1]_.
Bipartite graphs can also be matched using the functions present in
:mod:`networkx.algorithms.bipartite.matching`.
References
----------
.. [1] "Efficient Algorithms for Finding Maximum Matching in Graphs",
Zvi Galil, ACM Computing Surveys, 1986.
"""
#
# The algorithm is taken from "Efficient Algorithms for Finding Maximum
# Matching in Graphs" by Zvi Galil, ACM Computing Surveys, 1986.
# It is based on the "blossom" method for finding augmenting paths and
# the "primal-dual" method for finding a matching of maximum weight, both
# methods invented by Jack Edmonds.
#
# A C program for maximum weight matching by Ed Rothberg was used
# extensively to validate this new code.
#
# Many terms used in the code comments are explained in the paper
# by Galil. You will probably need the paper to make sense of this code.
#
class NoNode:
pass
class Blossom:
__slots__ = [ 'childs', 'edges', 'mybestedges' ]
def leaves(self):
for t in self.childs:
if isinstance(t, Blossom):
for v in t.leaves():
yield v
else:
yield t
gnodes = G.nodes()
maxweight = 0
allinteger = True
for i,j,wt in G.edges_iter(data=True):
if i != j and wt > maxweight:
maxweight = wt
mate = { }
label = { }
labeledge = { }
inblossom = dict(zip(gnodes, gnodes))
blossomparent = dict(zip(gnodes, repeat(None)))
blossombase = dict(zip(gnodes, gnodes))
bestedge = { }
dualvar = dict(zip(gnodes, repeat(maxweight)))
blossomdual = { }
allowedge = { }
queue = [ ]
def slack(v, w):
return dualvar[v] + dualvar[w] - 2 * G[v][w]
def assignLabel(w, t, v):
b = inblossom[w]
label[w] = label[b] = t
if v is not None:
labeledge[w] = labeledge[b] = (v, w)
else:
labeledge[w] = labeledge[b] = None
bestedge[w] = bestedge[b] = None
if t == 1:
if isinstance(b, Blossom):
queue.extend(b.leaves())
else:
queue.append(b)
elif t == 2:
base = blossombase[b]
assignLabel(mate[base], 1, base)
def scanBlossom(v, w):
path = [ ]
base = NoNode
while v is not NoNode:
b = inblossom[v]
if label[b] & 4:
base = blossombase[b]
break
path.append(b)
label[b] = 5
if labeledge[b] is None:
v = NoNode
else:
v = labeledge[b][0]
b = inblossom[v]
v = labeledge[b][0]
if w is not NoNode:
v, w = w, v
for b in path:
label[b] = 1
return base
def addBlossom(base, v, w):
bb = inblossom[base]
bv = inblossom[v]
bw = inblossom[w]
b = Blossom()
blossombase[b] = base
blossomparent[b] = None
blossomparent[bb] = b
b.childs = path = [ ]
b.edges = edgs = [ (v, w) ]
while bv != bb:
blossomparent[bv] = b
path.append(bv)
edgs.append(labeledge[bv])
v = labeledge[bv][0]
bv = inblossom[v]
path.append(bb)
path.reverse()
edgs.reverse()
while bw != bb:
blossomparent[bw] = b
path.append(bw)
edgs.append((labeledge[bw][1], labeledge[bw][0]))
w = labeledge[bw][0]
bw = inblossom[w]
label[b] = 1
labeledge[b] = labeledge[bb]
blossomdual[b] = 0
for v in b.leaves():
if label[inblossom[v]] == 2:
queue.append(v)
inblossom[v] = b
bestedgeto = { }
for bv in path:
if isinstance(bv, Blossom):
if bv.mybestedges is not None:
nblist = bv.mybestedges
bv.mybestedges = None
else:
nblist = [ (v, w)
for v in bv.leaves()
for w in G.neighbors_iter(v)
if v != w ]
else:
nblist = [ (bv, w)
for w in G.neighbors_iter(bv)
if bv != w ]
for k in nblist:
(i, j) = k
if inblossom[j] == b:
i, j = j, i
bj = inblossom[j]
if (bj != b and label.get(bj) == 1 and
((bj not in bestedgeto) or
slack(i, j) < slack(*bestedgeto[bj]))):
bestedgeto[bj] = k
bestedge[bv] = None
b.mybestedges = list(bestedgeto.values())
mybestedge = None
bestedge[b] = None
for k in b.mybestedges:
kslack = slack(*k)
if mybestedge is None or kslack < mybestslack:
mybestedge = k
mybestslack = kslack
bestedge[b] = mybestedge
def expandBlossom(b, endstage):
for s in b.childs:
blossomparent[s] = None
if isinstance(s, Blossom):
if endstage and blossomdual[s] == 0:
expandBlossom(s, endstage)
else:
for v in s.leaves():
inblossom[v] = s
else:
inblossom[s] = s
if (not endstage) and label.get(b) == 2:
entrychild = inblossom[labeledge[b][1]]
j = b.childs.index(entrychild)
if j & 1:
j -= len(b.childs)
jstep = 1
else:
jstep = -1
v, w = labeledge[b]
while j != 0:
if jstep == 1:
p, q = b.edges[j]
else:
q, p = b.edges[j-1]
label[w] = None
label[q] = None
assignLabel(w, 2, v)
allowedge[(p, q)] = allowedge[(q, p)] = True
j += jstep
if jstep == 1:
v, w = b.edges[j]
else:
w, v = b.edges[j-1]
allowedge[(v, w)] = allowedge[(w, v)] = True
j += jstep
bw = b.childs[j]
label[w] = label[bw] = 2
labeledge[w] = labeledge[bw] = (v, w)
bestedge[bw] = None
j += jstep
while b.childs[j] != entrychild:
bv = b.childs[j]
if label.get(bv) == 1:
j += jstep
continue
if isinstance(bv, Blossom):
for v in bv.leaves():
if label.get(v):
break
else:
v = bv
if label.get(v):
label[v] = None
label[mate[blossombase[bv]]] = None
assignLabel(v, 2, labeledge[v][0])
j += jstep
label.pop(b, None)
labeledge.pop(b, None)
bestedge.pop(b, None)
del blossomparent[b]
del blossombase[b]
del blossomdual[b]
def augmentBlossom(b, v):
t = v
while blossomparent[t] != b:
t = blossomparent[t]
if isinstance(t, Blossom):
augmentBlossom(t, v)
i = j = b.childs.index(t)
if i & 1:
j -= len(b.childs)
jstep = 1
else:
jstep = -1
while j != 0:
j += jstep
t = b.childs[j]
if jstep == 1:
w, x = b.edges[j]
else:
x, w = b.edges[j-1]
if isinstance(t, Blossom):
augmentBlossom(t, w)
j += jstep
t = b.childs[j]
if isinstance(t, Blossom):
augmentBlossom(t, x)
mate[w] = x
mate[x] = w
b.childs = b.childs[i:] + b.childs[:i]
b.edges = b.edges[i:] + b.edges[:i]
blossombase[b] = blossombase[b.childs[0]]
assert blossombase[b] == v
def augmentMatching(v, w):
for (s, j) in ((v, w), (w, v)):
while 1:
bs = inblossom[s]
if isinstance(bs, Blossom):
augmentBlossom(bs, s)
mate[s] = j
if labeledge[bs] is None:
break
t = labeledge[bs][0]
bt = inblossom[t]
s, j = labeledge[bt]
if isinstance(bt, Blossom):
augmentBlossom(bt, j)
mate[j] = s
while 1:
label.clear()
labeledge.clear()
bestedge.clear()
for b in blossomdual:
b.mybestedges = None
allowedge.clear()
queue[:] = [ ]
for v in gnodes:
if (v not in mate) and label.get(inblossom[v]) is None:
assignLabel(v, 1, None)
augmented = 0
while 1:
while queue and not augmented:
v = queue.pop()
assert label[inblossom[v]] == 1
for w in G.neighbors_iter(v):
if w == v:
continue # ignore self-loops
bv = inblossom[v]
bw = inblossom[w]
if bv == bw:
continue
if (v, w) not in allowedge:
kslack = slack(v, w)
if kslack <= 0:
allowedge[(v, w)] = allowedge[(w, v)] = True
if (v, w) in allowedge:
if label.get(bw) is None:
assignLabel(w, 2, v)
elif label.get(bw) == 1:
base = scanBlossom(v, w)
if base is not NoNode:
addBlossom(base, v, w)
else:
augmentMatching(v, w)
augmented = 1
break
elif label.get(w) is None:
label[w] = 2
labeledge[w] = (v, w)
elif label.get(bw) == 1:
if bestedge.get(bv) is None or kslack < slack(*bestedge[bv]):
bestedge[bv] = (v, w)
elif label.get(w) is None:
if bestedge.get(w) is None or kslack < slack(*bestedge[w]):
bestedge[w] = (v, w)
if augmented:
break
deltatype = -1
delta = deltaedge = deltablossom = None
if not maxcardinality:
deltatype = 1
delta = min(dualvar.values())
for v in gnodes:
if label.get(inblossom[v]) is None and bestedge.get(v) is not None:
d = slack(*bestedge[v])
if deltatype == -1 or d < delta:
delta = d
deltatype = 2
deltaedge = bestedge[v]
for b in blossomparent:
if ( blossomparent[b] is None and label.get(b) == 1 and
bestedge.get(b) is not None ):
kslack = slack(*bestedge[b])
if allinteger:
d = kslack // 2
else:
d = kslack / 2.0
if deltatype == -1 or d < delta:
delta = d
deltatype = 3
deltaedge = bestedge[b]
for b in blossomdual:
if ( blossomparent[b] is None and label.get(b) == 2 and
(deltatype == -1 or blossomdual[b] < delta) ):
delta = blossomdual[b]
deltatype = 4
deltablossom = b
if deltatype == -1:
deltatype = 1
delta = max(0, min(dualvar.values()))
for v in gnodes:
if label.get(inblossom[v]) == 1:
dualvar[v] -= delta
elif label.get(inblossom[v]) == 2:
dualvar[v] += delta
for b in blossomdual:
if blossomparent[b] is None:
if label.get(b) == 1:
blossomdual[b] += delta
elif label.get(b) == 2:
blossomdual[b] -= delta
if deltatype == 1:
break
elif deltatype == 2:
(v, w) = deltaedge
allowedge[(v, w)] = allowedge[(w, v)] = True
queue.append(v)
elif deltatype == 3:
(v, w) = deltaedge
allowedge[(v, w)] = allowedge[(w, v)] = True
queue.append(v)
elif deltatype == 4:
expandBlossom(deltablossom, False)
if not augmented:
break
for b in list(blossomdual.keys()):
if b not in blossomdual:
continue # already expanded
if ( blossomparent[b] is None and label.get(b) == 1 and
blossomdual[b] == 0 ):
expandBlossom(b, True)
max_weight = sum(G[u][v] for u, v in mate.items())//2
return max_weight
def read_data():
n = int(input())
F = [list(map(int, input().split())) for _ in range(n)]
return n, F
def solve(n, F):
Es = [dict() for _ in range(n)]
for u, f in enumerate(F):
for v, w in enumerate(f):
if v == u:continue
Es[u][v] = w
G = Graph(Es)
return max_weight_matching(G)
n, F = read_data()
print(solve(n, F))