test/aoj/1040.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1040

Depends on

• Minimum Steiner Tree (graph/minimum_steiner_tree.hpp)

Code

#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;
    }
}

Back to top page