結果
| 問題 |
No.519 アイドルユニット
|
| コンテスト | |
| ユーザー |
 はまやんはまやん
|
| 提出日時 | 2017-08-08 10:48:14 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 1,000 ms |
| コード長 | 20,615 bytes |
| コンパイル時間 | 4,049 ms |
| コンパイル使用メモリ | 226,352 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-10-12 00:09:19 |
| 合計ジャッジ時間 | 4,719 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 34 |
ソースコード
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template <typename WeightType>
class MaximumWeightedMatching {
/*
Maximum Weighted Matching in General Graphs
- O(n^3) time
- O(n + m) space
Note: each vertex is 1-indexed.
*/
public:
using i8 = signed char;
using i64 = long long;
using weight_t = WeightType;
using weight_sum_t = i64;
struct Edge { int from, to; weight_t weight; Edge(int a, int b, weight_t c) : from(a), to(b), weight(c) {}
Edge() {} };
private:
enum TreeLabelNumber { INNER = -1, UNUSED = 0, OUTER = 1 };
enum LabelNumber { SEPARATED = -2, DEFAULT = -1 };
enum EdgeNumber { UNDEFINED = 1 << 30 };
static constexpr weight_t INF = weight_t(1) << (sizeof(weight_t) * 8 - 2);
struct Node { int next, from, to; };
struct Label { int from, to; };
struct LinkedList { int eid, next; };
class Queue {
public:
Queue() {}
Queue(int N) : que(N), qh(0), qt(0) {}
void clear() { qh = qt = 0; }
int* data() { return que.data(); }
bool empty() const { return qh == qt; }
int dequeue() { return que[qh++]; }
void enqueue(int u) { que[qt++] = u; }
int operator [] (int i) const { return que[i]; }
int size() const { return qt; }
vector<int> que;
int qh, qt;
};
public:
MaximumWeightedMatching(int N, const vector<Edge>& raw_edges)
: N(N), B((N - 1) / 2), size(N + B + 1) {
offsets.assign(N + 2, 0);
for (auto& e : raw_edges) {
offsets[e.from + 1]++;
offsets[e.to + 1]++;
}
rep(i, 1, N + 1) offsets[i] += offsets[i - 1];
edges.resize(raw_edges.size() * 2);
rep(i, 0, raw_edges.size()) {
auto& e = raw_edges[i];
edges[offsets[e.from]++] = { e.from, e.to, 2 * e.weight };
edges[offsets[e.to]++] = { e.to, e.from, 2 * e.weight };
}
rep(i, 0, N + 1) offsets[N + 1 - i] = offsets[N - i];
offsets[0] = 0;
}
weight_sum_t maximum_weighted_matching() {
initialize();
set_potential();
rep(u, 1, N + 1) if (!mate[u]) {
for (int s = 0; !augmented(u, s); s = adjust_dual_solutions());
fix_blossom_bases();
clear_label();
}
weight_sum_t ret = 0;
rep(u, 1, N + 1) if (mate[u] > u) {
weight_t max_w = 0;
rep(eid, offsets[u], offsets[u + 1]) if (edges[eid].to == mate[u]) {
max_w = max(max_w, edges[eid].weight);
}
ret += max_w;
}
return ret >> 1;
}
private:
inline int encode(int e) const {
return e + size + 1; // should be >= 3
}
inline weight_t reduced_cost(int u, int v, const Edge& e) const {
return potential[u] + potential[v] - e.weight;
}
inline weight_t reduced_cost(int eid) const {
return reduced_cost(edges[eid].from, edges[eid].to, edges[eid]);
}
void rematch(int v, int w) {
auto t = mate[v]; mate[v] = w;
if (mate[t] != v) return;
if (label[v].to == 0) {
mate[t] = label[v].from;
rematch(mate[t], t);
}
else {
int x = label[v].from, y = label[v].to;
rematch(x, y); rematch(y, x);
}
}
Label search_blossom_edge(int bid) const {
int b = base[bid], bv = b;
for (; node[bv].next != b; bv = node[node[bv].next].next);
return { node[bv].from, node[bv].to };
}
void label_blossom(int bid, int m, Label l) {
label[bid] = { l.from, (l.to == surface[l.to]) ? 0 : l.to };
if (bid <= N) return;
int b = base[bid]; label_blossom(b, mate[bid] = m, l);
l = search_blossom_edge(bid);
for (int bv = b, bw; node[bv].next != b; bv = node[bw].next) {
label_blossom(bw = node[bv].next, 0, l);
label_blossom(node[bw].next, node[bw].from, { node[bv].from, node[bv].to });
}
}
int find_mate(int bid) {
return bid <= N ? mate[bid] : mate[bid] = find_mate(base[bid]);
}
void push_inner_blossom_rec(int bid, bool push = true) {
tree_label[bid] = (bid <= N) ? INNER : UNUSED;
if (bid > N) {
int v = base[bid], u = v;
do { push_inner_blossom_rec(v, push); } while ((v = node[v].next) != u);
}
else if (push) inner_vertices[inner_vertices_size++] = bid;
}
void push_inner_blossom(int bid) {
if (tree_label[bid] != UNUSED) return;
bool push = label[bid].from != SEPARATED;
if (bid > N) {
if (push) inner_blossoms[inner_blossom_size++] = bid;
push_inner_blossom_rec(bid, push);
}
else if (push) inner_vertices[inner_vertices_size++] = bid;
tree_label[bid] = INNER;
}
void push_outer_blossom_rec(int bid) {
tree_label[bid] = (bid <= N) ? OUTER : UNUSED;
if (bid > N) {
int v = base[bid], u = v;
do { push_outer_blossom_rec(v); } while ((v = node[v].next) != u);
}
else outer_vertices.enqueue(bid);
}
void push_outer_blossom(int bid, bool push) {
push_outer_blossom_rec(bid);
if (bid <= N) return;
if (push) outer_blossoms[outer_blossom_size++] = bid, tree_label[bid] = OUTER;
else tree_label[bid] = UNUSED;
}
inline void merge_edge(int x, int bx, int eid) {
auto& e = edges[eid];
int y = e.to, by = surface[y];
if (tree_label[by] != OUTER || bx == by) return;
auto r_cost = reduced_cost(x, y, e);
if (r_cost < best_cost[by].first) {
if (best_cost[by].first == INF) merged_edges[merged_edge_size++] = by;
best_cost[by] = { r_cost, eid };
}
}
inline void merge_vertex(int x, int bx) {
rep(eid, offsets[x], offsets[x + 1]) merge_edge(x, bx, eid);
best_edge[x] = UNDEFINED;
}
void clear_best_edges(int b) {
if (b > N) {
int v = b = base[b];
do { clear_best_edges(v); } while ((v = node[v].next) != b);
}
else best_edge[b] = UNDEFINED;
}
void merge_outer(int b, int bid) {
if (b > N) {
for (int head = blist_head[b]; head >= 0; head = bnode[head].next) {
int eid = bnode[head].eid;
merge_edge(edges[eid].from, bid, eid);
next_bnode.push_back(head);
}
blist_head[b] = -1;
clear_best_edges(b);
}
else merge_vertex(b, bid);
}
void merge_inner(int b, int bid) {
if (b > N) {
int v = b = base[b];
do { merge_inner(v, bid); } while ((v = node[v].next) != b);
}
else merge_vertex(b, bid);
}
void build_linked_list(int bid) {
if (bid <= N) return;
int last = -1;
for (; merged_edge_size > 0; ) {
int nid = next_bnode.back(); next_bnode.pop_back();
int by = merged_edges[--merged_edge_size], eid = best_cost[by].second;
int x = edges[eid].from, y = edges[eid].to;
bnode[nid] = { eid, last };
if (tree_label[y] == OUTER) update_best_edge(y, by, best_cost[by].first, eid);
if (best_edge[x] == UNDEFINED || best_cost[by].first < reduced_cost(best_edge[x])) {
best_edge[x] = eid;
}
best_cost[by] = { INF, UNDEFINED };
last = nid;
}
blist_head[bid] = last;
}
void merge_best_edges(int bid, int inner_count) {
rep(i, 0, inner_count) {
int bv = outer_blossoms[outer_blossom_size + i];
if (bv >= 0) merge_outer(bv, bid), merge_inner(node[bv].next, bid);
else merge_inner(~bv, bid), merge_outer(node[~bv].next, bid);
}
merge_outer(base[bid], bid);
build_linked_list(bid);
}
void contract(int x, int y, int eid) {
int s = surface[x], t = surface[y];
if (s == t) return;
auto h = label[surface[mate[s]]].from = label[surface[mate[t]]].from = -encode(eid);
int lca = -1;
for (; ; label[surface[mate[s]]].from = h) {
if (mate[t] != 0) swap(s, t);
s = lca = surface[label[s].from];
if (label[surface[mate[s]]].from == h) break;
}
int inner_count = 0;
for (int dir = 0; dir < 2; ++dir) {
int v = (dir == 0) ? x : y;
while (1) {
int bv = surface[v], mv = mate[bv], bmv = surface[mv];
if (bv == lca) break;
label[mv] = label[bmv] = { x, y };
auto n = node[bmv];
if (!dir) {
node[bv] = { bmv, mate[mv], mv };
node[bmv].next = surface[n.to];
}
else {
node[surface[n.to]] = { bmv, n.to, n.from };
node[bmv] = { bv, mv, mate[mv] };
}
push_outer_blossom(bmv, false);
v = label[bv].from;
// Caution: used as temporary array
outer_blossoms[outer_blossom_size + (inner_count++)] = !dir ? bv : ~bmv;
}
}
node[surface[y]] = { surface[x], y, x };
int bid = next_bid.back(); next_bid.pop_back();
base[bid] = lca, label[bid].from = label[lca].from, mate[bid] = mate[lca];
tree_label[bid] = OUTER;
set_surface(bid, bid);
merge_best_edges(bid, inner_count);
outer_blossoms[outer_blossom_size++] = bid;
}
inline void update_best_edge(int y, int by, weight_t r_cost, int eid) {
if (tree_label[by] != OUTER && best_edge[y] == UNDEFINED) {
neighbors[neighbor_size++] = y;
}
if (best_edge[y] == UNDEFINED || r_cost < reduced_cost(best_edge[y])) {
best_edge[y] = eid;
}
}
void build_edge_list(int b) {
if (b <= N) return;
merge_inner(b, b);
build_linked_list(b);
}
bool augmented(int root, int s) {
if (s == 0) {
int br = surface[root];
push_outer_blossom(br, true);
label_blossom(br, 0, { 0, 0 });
build_edge_list(br);
}
for (; !outer_vertices.empty() || s > 0; s = 0) {
auto x = (s > 0) ? s : outer_vertices.dequeue();
if (potential[x] == 0) {
if (root != x) rematch(x, 0);
return true;
}
rep(eid, offsets[x], offsets[x + 1]) {
int bx = surface[x], y = edges[eid].to, by = surface[y];
if (bx == by) continue;
auto r_cost = reduced_cost(x, y, edges[eid]);
if (r_cost > 0 || tree_label[by] != OUTER) {
update_best_edge(y, by, r_cost, eid);
if (r_cost > 0) continue;
}
if (label[by].from >= 0) {
contract(x, y, eid);
continue;
}
if (tree_label[by] == UNUSED) {
push_inner_blossom(by);
if (by != y) label_blossom(by, find_mate(by), { DEFAULT, 0 });
}
int z = mate[by];
if (z == 0 && by != surface[root]) {
rematch(x, y); rematch(y, x);
return true;
}
int bz = surface[z];
if (label[bz].from < 0) {
node[by] = { -1, y, x };
push_outer_blossom(bz, true);
label_blossom(bz, mate[z], { x, y });
build_edge_list(bz);
}
}
}
return false;
}
void set_surface(int b, int bid) {
for (int v = base[b]; surface[v] != bid; v = node[v].next) {
if (v > N) tree_label[v] = UNUSED, set_surface(v, bid);
surface[v] = bid;
}
}
void reset_surface(int b, int bid) {
surface[b] = bid;
if (b <= N) return;
for (b = base[b]; surface[b] != bid; b = node[b].next) reset_surface(b, bid);
}
void separate_blossom(int bid, bool push_blossom = true) {
tree_label[bid] = UNUSED, label[bid].from = SEPARATED;
if (bid <= N) return;
if (push_blossom) inner_blossoms[inner_blossom_size++] = bid;
for (int b = base[bid]; label[b].from != SEPARATED; b = node[b].next) {
separate_blossom(b, false);
}
}
void reverse_blossom(int b) {
int v = b, fr = node[b].from, to = node[b].to;
for (int nv = node[v].next; nv != b; ) {
int nnext = node[nv].next, nfr = node[nv].from, nto = node[nv].to;
node[nv].next = v, node[nv].from = to, node[nv].to = fr;
fr = nfr, to = nto, v = nv, nv = nnext;
}
node[b].next = v, node[b].from = to, node[b].to = fr;
}
void expand_blossom(int bid) {
next_bid.push_back(bid); tree_label[bid] = UNUSED;
for (int b = base[bid]; surface[b] == bid; b = node[b].next) reset_surface(b, b);
int old_base = base[bid], target = surface[node[bid].from];
if (mate[node[target].from] == node[target].to) reverse_blossom(old_base);
for (int b = target; node[b].next != old_base; ) {
separate_blossom(b = node[b].next); separate_blossom(b = node[b].next);
}
node[target] = node[bid];
for (int b = old_base; ; b = node[b].next) {
label[b].from = DEFAULT, tree_label[b] = INNER;
if (b > N) inner_blossoms[inner_blossom_size++] = b;
int m = find_mate(b), bm = surface[m];
if (b != old_base) mate[bm] = mate[m];
label[m] = label[bm] = { node[b].to, node[b].from };
if (b == target) break;
push_outer_blossom(b = node[b].next, true);
build_edge_list(b);
}
base[bid] = bid, surface[bid] = bid;
}
void update_potential(int* vs, int s, weight_t delta, int label) {
rep(i, 0, s) {
int x = vs[i];
if (tree_label[x] != label) continue;
potential[x] += delta;
}
}
int adjust_dual_solutions() {
pair<weight_t, int> delta1(INF, 0), delta2(INF, 0), delta3(INF, 0), delta4(INF, 0);
rep(i, 0, outer_vertices.size()) {
int y = outer_vertices[i], eid = best_edge[y];
delta1 = min(delta1, { potential[y], y });
if (eid != UNDEFINED) {
delta3 = min(delta3, { reduced_cost(eid) >> 1, y });
}
}
rep(i, 0, neighbor_size) {
int y = neighbors[i];
if (tree_label[y] == UNUSED) {
int eid = best_edge[y], x = edges[eid].from;
delta2 = min(delta2, { reduced_cost(x, y, edges[eid]), x });
}
}
rep(i, 0, inner_blossom_size) if (tree_label[inner_blossoms[i]] == INNER) {
int b = inner_blossoms[i];
delta4 = min(delta4, { potential[b] >> 1, b });
}
auto delta = min(min(delta1, delta2), min(delta3, delta4));
auto d = delta.first;
update_potential(outer_vertices.data(), outer_vertices.size(), -1 * d, OUTER);
update_potential(inner_vertices.data(), inner_vertices_size, 1 * d, INNER);
update_potential(outer_blossoms.data(), outer_blossom_size, 2 * d, OUTER);
update_potential(inner_blossoms.data(), inner_blossom_size, -2 * d, INNER);
if (delta4.first == d) {
expand_blossom(delta4.second);
return -1;
}
else {
return delta.second;
}
}
void fix_blossom_bases() {
int remain = size - next_bid.size() - (N + 1);
for (int bid = N + 1; bid < size && remain > 0; ++bid) if (base[bid] != bid) {
int b = base[bid];
for (int skipped = 0; skipped < 2;) {
b = node[b].next;
if (mate[node[b].from] == node[b].to) skipped = 0;
else skipped++;
}
base[bid] = b;
--remain;
}
}
void free_edge_list(int x) {
for (int head = blist_head[x]; head >= 0; head = bnode[head].next) {
next_bnode.push_back(head);
}
blist_head[x] = -1;
}
void clear_vertices(int* vs, int size) {
rep(i, 0, size) {
int v = vs[i];
label[v] = { DEFAULT, 0 }; tree_label[v] = UNUSED; best_edge[v] = UNDEFINED;
}
}
void clear_label() {
label[0] = { DEFAULT, 0 };
clear_vertices(outer_vertices.data(), outer_vertices.size()); outer_vertices.clear();
clear_vertices(inner_vertices.data(), inner_vertices_size); inner_vertices_size = 0;
clear_vertices(outer_blossoms.data(), outer_blossom_size);
rep(i, 0, outer_blossom_size) if (blist_head[outer_blossoms[i]] >= 0) free_edge_list(outer_blossoms[i]);
outer_blossom_size = 0;
clear_vertices(inner_blossoms.data(), inner_blossom_size); inner_blossom_size = 0;
rep(i, 0, neighbor_size) best_edge[neighbors[i]] = UNDEFINED;
neighbor_size = 0;
}
void set_potential() {
potential.resize(size);
rep(u, 1, N + 1) {
weight_t max_w = 0;
rep(eid, offsets[u], offsets[u + 1]) max_w = max(max_w, edges[eid].weight);
potential[u] = max_w >> 1;
}
}
void initialize() {
mate.assign(size, 0);
label.assign(size, { -1, 0 });
surface.resize(size); rep(i, 0, size) surface[i] = i;
base.resize(size); rep(i, 0, size) base[i] = i;
node.resize(size); rep(i, 0, size) node[i] = { i, i, i };
outer_vertices = Queue(N);
inner_vertices.resize(N + 1); inner_vertices_size = 0;
outer_blossoms.resize(B); outer_blossom_size = 0;
inner_blossoms.resize(B); inner_blossom_size = 0;
tree_label.assign(size, UNUSED);
next_bid.resize(B);
rep(i, 0, B) next_bid[i] = size - 1 - i;
merged_edges.resize(N + 1); merged_edge_size = 0;
best_cost.assign(size, { INF, UNDEFINED });
neighbors.resize(N + 1); neighbor_size = 0;
best_edge.assign(size, UNDEFINED);
blist_head.assign(size, -1);
next_bnode.resize(edges.size());
rep(i, 0, edges.size()) next_bnode[i] = edges.size() - 1 - i;
bnode.resize(edges.size());
}
private:
int N, B, size;
vector<Edge> edges;
vector<int> offsets;
vector<Label> label;
vector<int> mate, surface, base;
vector<Node> node;
vector<weight_t> potential;
vector<int> next_bid;
vector<i8> tree_label;
Queue outer_vertices;
vector<int> inner_vertices; int inner_vertices_size;
vector<int> outer_blossoms; int outer_blossom_size;
vector<int> inner_blossoms; int inner_blossom_size;
vector<int> merged_edges; int merged_edge_size;
vector< pair<weight_t, int> > best_cost;
vector<int> neighbors; int neighbor_size;
vector<int> best_edge;
vector<int> blist_head;
vector<LinkedList> bnode;
vector<int> next_bnode;
};
/*---------------------------------------------------------------------------------------------------
∧＿∧
∧＿∧ （´<_｀ ） Welcome to My Coding Space!
（ ´_ゝ`） / ⌒i
／ ＼ | |
/ /￣￣￣￣/ |
＿_(__ﾆつ/ ＿/ .| .|＿＿＿＿
＼/＿＿＿＿/ （u ⊃
---------------------------------------------------------------------------------------------------*/
typedef MaximumWeightedMatching<int> MWM;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N;
vector<MWM::Edge> e;
rep(a, 0, N) rep(b, 0, N) {
int c; cin >> c;
if (a < b && 0 <= c) e.push_back(MWM::Edge(a + 1, b + 1, c));
}
MWM m(N, e);
int ans = m.maximum_weighted_matching();
cout << ans << endl;
}