結果
| 問題 | No.519 アイドルユニット |
| ユーザー |
 Min_25
|
| 提出日時 | 2017-05-28 21:44:08 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 18,083 bytes |
| コンパイル時間 | 1,407 ms |
| コンパイル使用メモリ | 107,096 KB |
| 最終ジャッジ日時 | 2025-02-07 16:30:57 |
| 合計ジャッジ時間 | 2,086 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:580:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
580 | int w; scanf("%d", &w);
| ~~~~~^~~~~~~~~~
In file included from /usr/include/c++/13/string:43,
from /usr/include/c++/13/bits/locale_classes.h:40,
from /usr/include/c++/13/bits/ios_base.h:41,
from /usr/include/c++/13/ios:44,
from /usr/include/c++/13/ostream:40,
from /usr/include/c++/13/iostream:41,
from main.cpp:10:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<MaximumWeightedMatching<int>::Edge, std::allocator<MaximumWeightedMatching<int>::Edge> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = MaximumWeightedMatching<int>::Edge]’: target specific option mismatch
184 | ~allocator() _GLIBCXX_NOTHROW { }
| ^
In file included from /usr/include/c++/13/vector:66,
from main.cpp:11:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
133 | struct _Vector_impl
| ^~~~~~~~~~~~
ソースコード
#pragma GCC optimize ("O3")#pragma GCC target ("avx")#include <cstdio>#include <cassert>#include <cmath>#include <cstring>#include <algorithm>#include <iostream>#include <vector>#include <functional>#include <utility>#include <set>#include <map>#include <queue>#define _rep(_1, _2, _3, _4, name, ...) name#define rep2(i, n) rep3(i, 0, n)#define rep3(i, a, b) rep4(i, a, b, 1)#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)using namespace std;using i64 = long long;using u32 = unsigned;using u64 = unsigned long long;using f80 = long double;using i8 = signed char;template <typename WeightType>class MaximumWeightedMatching {/*Maximum Weighted Matching in General Graphs- O(n^3) time- O(n + m) spaceNote: each vertex is 1-indexed.*/public:using weight_t = WeightType;using weight_sum_t = i64;struct Edge { int from, to; weight_t weight; };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, 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, 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, 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 arrayouter_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, 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, 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, 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, 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, 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, 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, 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, size) surface[i] = i;base.resize(size); rep(i, size) base[i] = i;node.resize(size); rep(i, 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, 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, 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;};void solve() {int N;while (~scanf("%d", &N)) {using Edge = MaximumWeightedMatching<int>::Edge;vector<Edge> edges;rep(i, N) rep(j, N) {int w; scanf("%d", &w);edges.push_back({i + 1, j + 1, w});}auto MWM = MaximumWeightedMatching<int>(N, edges);auto ans = MWM.maximum_weighted_matching();printf("%lld\n", ans);}}int main() {clock_t beg = clock();solve();clock_t end = clock();fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);return 0;}