sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1040" #include <bits/stdc++.h> #include "../../graph/minimum_steiner_tree.hpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); while (true) { int H, W; cin >> H >> W; if (H == 0) break; vector<vector<pair<int, int>>> G(H * W); vector<int> terminals; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { int s; cin >> s; if (s) terminals.push_back(i * W + j); if (i < H - 1) { G[i * W + j].push_back({(i + 1) * W + j, 1}); G[(i + 1) * W + j].push_back({i * W + j, 1}); } if (j < W - 1) { G[i * W + j].push_back({i * W + j + 1, 1}); G[i * W + j + 1].push_back({i * W + j, 1}); } } } cout << H * W - minimum_steiner_tree(G, terminals) - 1 << endl; } }
#line 1 "test/aoj/1040.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1040" #include <bits/stdc++.h> #line 7 "graph/minimum_steiner_tree.hpp" template <typename T> T minimum_steiner_tree(std::vector<std::vector<std::pair<int, T>>>& G, std::vector<int>& terminals) { const int n = G.size(); const int t = terminals.size(); constexpr T INF = std::numeric_limits<T>::max() / 2; using P = std::pair<T, int>; std::vector<std::vector<T>> dp(1 << t, std::vector<T>(n, INF)); for (int i = 0; i < t; ++i) dp[1 << i][terminals[i]] = 0; for (int S = 1; S < (1 << t); ++S) { for (int i = 0; i < n; ++i) { for (int U = S; U > 0; U = (U - 1) & S) { dp[S][i] = std::min(dp[S][i], dp[S ^ U][i] + dp[U][i]); } } if (S == (1 << t) - 1) continue; std::priority_queue<P, std::vector<P>, std::greater<>> pq; for (int i = 0; i < n; ++i) { pq.emplace(dp[S][i], i); } while (!pq.empty()) { auto [d, v] = pq.top(); pq.pop(); if (dp[S][v] < d) continue; for (auto [u, w] : G[v]) { if (dp[S][u] > d + w) { dp[S][u] = d + w; pq.emplace(dp[S][u], u); } } } } return dp.back()[terminals[0]]; } #line 6 "test/aoj/1040.test.cpp" using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); while (true) { int H, W; cin >> H >> W; if (H == 0) break; vector<vector<pair<int, int>>> G(H * W); vector<int> terminals; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { int s; cin >> s; if (s) terminals.push_back(i * W + j); if (i < H - 1) { G[i * W + j].push_back({(i + 1) * W + j, 1}); G[(i + 1) * W + j].push_back({i * W + j, 1}); } if (j < W - 1) { G[i * W + j].push_back({i * W + j + 1, 1}); G[i * W + j + 1].push_back({i * W + j, 1}); } } } cout << H * W - minimum_steiner_tree(G, terminals) - 1 << endl; } }