結果
問題 | No.114 遠い未来 |
ユーザー | ruthen71 |
提出日時 | 2024-07-28 14:12:44 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,291 ms / 5,000 ms |
コード長 | 8,406 bytes |
コンパイル時間 | 2,930 ms |
コンパイル使用メモリ | 130,208 KB |
実行使用メモリ | 13,440 KB |
最終ジャッジ日時 | 2024-07-28 14:12:54 |
合計ジャッジ時間 | 9,832 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
6,812 KB |
testcase_01 | AC | 536 ms
13,184 KB |
testcase_02 | AC | 115 ms
6,944 KB |
testcase_03 | AC | 28 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 5 ms
6,940 KB |
testcase_06 | AC | 416 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,948 KB |
testcase_09 | AC | 8 ms
6,940 KB |
testcase_10 | AC | 79 ms
6,944 KB |
testcase_11 | AC | 190 ms
8,448 KB |
testcase_12 | AC | 529 ms
13,312 KB |
testcase_13 | AC | 557 ms
13,440 KB |
testcase_14 | AC | 373 ms
6,940 KB |
testcase_15 | AC | 1,291 ms
6,940 KB |
testcase_16 | AC | 184 ms
6,940 KB |
testcase_17 | AC | 184 ms
6,944 KB |
testcase_18 | AC | 1,098 ms
6,940 KB |
testcase_19 | AC | 96 ms
6,940 KB |
testcase_20 | AC | 124 ms
6,940 KB |
testcase_21 | AC | 7 ms
6,944 KB |
testcase_22 | AC | 8 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 4 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 3 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
ソースコード
// #include <iostream> // // #include "graph/read_graph.hpp" // #include "graph/minimum_steiner_tree.hpp" // // int main() { // int N, M, T; // std::cin >> N >> M >> T; // auto g = read_graph<long long>(N, M, true); // std::vector<int> terminals(T); // for (int i = 0; i < T; i++) { // std::cin >> terminals[i]; // terminals[i]--; // } // if (T <= 15) { // auto dp = minimum_steiner_tree(g, terminals, 1'000'000'000'000'000'000LL); // std::cout << dp.back()[terminals[0]] << '\n'; // } else { // std::cout << minimum_steiner_tree_mst(g, terminals, 1'000'000'000'000'000'000LL) << '\n'; // } // return 0; // } #include <iostream> #include <vector> template <class T> struct Edge { int from, to; T cost; int id; Edge() = default; Edge(int from, int to, T cost = 1, int id = -1) : from(from), to(to), cost(cost), id(id) {} friend std::ostream& operator<<(std::ostream& os, const Edge<T>& e) { // output format: "{ id : from -> to, cost }" return os << "{ " << e.id << " : " << e.from << " -> " << e.to << ", " << e.cost << " }"; } }; template <class T> using Edges = std::vector<Edge<T>>; template <class T> using Graph = std::vector<std::vector<Edge<T>>>; template <class T> Graph<T> read_graph(const int n, const int m, const bool weight = false, const bool directed = false, const int offset = 1) { Graph<T> g(n); for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; a -= offset, b -= offset; if (weight) { T c; std::cin >> c; if (!directed) g[b].push_back(Edge(b, a, c, i)); g[a].push_back(Edge(a, b, c, i)); } else { // c = 1 if (!directed) g[b].push_back(Edge(b, a, T(1), i)); g[a].push_back(Edge(a, b, T(1), i)); } } return g; } template <class T> Graph<T> read_parent(const int n, const bool weight = false, const bool directed = false, const int offset = 1) { Graph<T> g(n); for (int i = 1; i < n; i++) { int p; std::cin >> p; p -= offset; if (weight) { T c; std::cin >> c; if (!directed) g[i].push_back(Edge(i, p, c, i - 1)); g[p].push_back(Edge(p, i, c, i - 1)); } else { // c = 1 if (!directed) g[i].push_back(Edge(i, p, T(1), i - 1)); g[p].push_back(Edge(p, i, T(1), i - 1)); } } return g; } #include <queue> #include <algorithm> #include <cassert> struct UnionFind { int n; std::vector<int> parents; UnionFind() {} UnionFind(int n) : n(n), parents(n, -1) {} int leader(int x) { return parents[x] < 0 ? x : parents[x] = leader(parents[x]); } bool merge(int x, int y) { x = leader(x), y = leader(y); if (x == y) return false; if (parents[x] > parents[y]) std::swap(x, y); parents[x] += parents[y]; parents[y] = x; return true; } bool same(int x, int y) { return leader(x) == leader(y); } int size(int x) { return -parents[leader(x)]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(n), group_size(n); for (int i = 0; i < n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(n); for (int i = 0; i < n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < n; i++) { result[leader_buf[i]].push_back(i); } result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } void init(int n) { parents.assign(n, -1); } // reset }; // minimum steiner tree // O(3 ^ k n + 2 ^ k m \log m) (n = |V|, m = |E|, k = |terminals|) // https://www.slideshare.net/wata_orz/ss-12131479#50 // https://kopricky.github.io/code/Academic/steiner_tree.html // https://atcoder.jp/contests/abc364/editorial/10547 template <class T> std::vector<std::vector<T>> minimum_steiner_tree(const Graph<T>& g, const std::vector<int>& terminals, const T inf) { const int n = (int)(g.size()); const int k = (int)(terminals.size()); const int k2 = 1 << k; // dp[bit][v] = ターミナルの部分集合が bit (0 ~ k - 1 に圧縮), 加えて頂点 v も含まれる最小シュタイナー木 std::vector dp(k2, std::vector<T>(n, inf)); for (int i = 0; i < k; i++) dp[1 << i][terminals[i]] = T(0); for (int bit = 0; bit < (1 << k); bit++) { // dp[bit][v] = min(dp[bit][v], dp[sub][v] + dp[bit ^ sub][v]) // 通常の実装 // for (int sub = bit; sub > 0; sub = (sub - 1) & bit) { // 定数倍高速化 // bit の中で 1 要素だけ sub と bit ^ sub のどちらに属するか決める int bit2 = bit ^ (bit & -bit); for (int sub = bit2; sub > 0; sub = (sub - 1) & bit2) { for (int v = 0; v < n; v++) { dp[bit][v] = std::min(dp[bit][v], dp[sub][v] + dp[bit ^ sub][v]); } } // dp[bit][v] = min(dp[bit][v], dp[bit][u] + cost(u, v)) using tp = std::pair<T, int>; std::priority_queue<tp, std::vector<tp>, std::greater<tp>> que; for (int u = 0; u < n; u++) que.emplace(dp[bit][u], u); while (!que.empty()) { auto [d, u] = que.top(); que.pop(); if (dp[bit][u] != d) continue; for (auto&& e : g[u]) { if (dp[bit][e.to] > d + e.cost) { dp[bit][e.to] = d + e.cost; que.emplace(dp[bit][e.to], e.to); } } } } // dp[k2 - 1][i] = ターミナルと頂点 i を含む最小シュタイナー木 // dp[k2 - 1][terminals[0]] が基本的な答えになる return dp; } // O(2 ^ {n - k} (n + m)) (n = |V|, m = |E|, k = |terminals|) // https://yukicoder.me/problems/no/114/editorial // n - k <= 20 template <class T> T minimum_steiner_tree_mst(const Graph<T>& g, const std::vector<int>& terminals, const T inf) { const int n = (int)(g.size()); const int k = (int)(terminals.size()); // ターミナルに含まれない点集合 (others) を取得 std::vector<int> used(n, 0); for (int i = 0; i < k; i++) used[terminals[i]] = 1; std::vector<int> others; for (int i = 0; i < n; i++) { if (used[i] == 0) others.push_back(i); } // 辺のリスト std::vector<Edge<T>> edges; for (int v = 0; v < n; v++) { for (auto&& e : g[v]) { if (e.from < e.to) edges.push_back(e); } } std::sort(edges.begin(), edges.end(), [&](Edge<T>& a, Edge<T>& b) -> bool { return a.cost < b.cost; }); // ターミナル + others の組合せを全列挙 -> Minimum Spanning Tree を求める T ans = inf; for (int bit = 0; bit < (1 << (n - k)); bit++) { // 使う頂点集合 (used) を計算 for (int i = 0; i < n - k; i++) used[others[i]] = bit >> i & 1; // Minimum Spanning Tree を計算 UnionFind uf(n); T cur = 0; int connected = 0; for (auto&& e : edges) { // subv に対する g の誘導部分グラフに含まれる辺のみ試す if (!(used[e.from] and used[e.to])) continue; if (!uf.same(e.from, e.to)) { uf.merge(e.from, e.to); cur += e.cost; connected++; } } // 全域木が作れたか判定 if (connected + 1 == k + __builtin_popcount(bit)) ans = std::min(ans, cur); // used をもとに戻す for (int i = 0; i < n - k; i++) used[others[i]] = 0; } return ans; } int main() { int N, M, T; std::cin >> N >> M >> T; auto g = read_graph<long long>(N, M, true); std::vector<int> terminals(T); for (int i = 0; i < T; i++) { std::cin >> terminals[i]; terminals[i]--; } if (T <= 15) { auto dp = minimum_steiner_tree(g, terminals, 1'000'000'000'000'000'000LL); std::cout << dp.back()[terminals[0]] << '\n'; } else { std::cout << minimum_steiner_tree_mst(g, terminals, 1'000'000'000'000'000'000LL) << '\n'; } return 0; }