BZOJ 3776 流星雨

这题看上去那么简单，但是没人过，于是我去试了一下。然后也没有过，但是我坚信我的算法没有错，于是怀疑数据错了。正要向管理员理论时，想到是不是数据的格式有问题，然后马上改了一发。然后就AC了。。。。

题目大意

给你一个正六边形土地，边长为\(n\)。然后其中有四个联通块，要求你用最少的材料使他们联通。

数据规模：\(1 \le n \le 20\)

题目分析

首先这个是一个很显然的Steiner Tree模型，我们把那四个联通块当作特殊点，于是就只要套个模板就好了。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int dx[] = { 0, -1, -1,  0, +1, +1};
const int dy[] = {-2, -1, +1, +2, +1, -1};
const int MAXN = 2000 + 10, SIZE = 500 + 10;

int id[SIZE][SIZE], R, C;
char d[SIZE][SIZE];

inline bool fit(int x, int y) {
    return x >= 1 && x <= R && y >= 0 && y <= C;
}

inline bool island(char c) {
    return c == '.' || c == 'A' || c == 'B' || c == 'C' || c == 'D';
}

inline bool ok(char c) {
    return c == 'A' || c == 'B' || c == 'C' || c == 'D';
}

void bfs(int x, int y, char c) {
    queue<PII> Q; Q.push(PII(x, y)); id[x][y] = c - 'A';
    while (!Q.empty()) {
        x = Q.front().first, y = Q.front().second; Q.pop();
        for (int i = 0; i < 6; ++ i) {
            int xx = x + dx[i], yy = y + dy[i];
            if (!fit(xx, yy) || !ok(d[xx][yy])) continue;
            if (d[xx][yy] == c && id[xx][yy] == -1) {
                id[xx][yy] = c - 'A';
                Q.push(PII(xx, yy));
            }
        }
    }
}

vector<int> G[MAXN];
int vis[MAXN], dp[1 << 4][MAXN];
int cost[MAXN], N;

void build() {
    for (int i = 0; i < N; ++ i) G[i].clear();
    for (int i = 1; i <= R; ++ i) {
        for (int j = 0; j <= C; ++ j) {
            if (!island(d[i][j])) continue;
            int u = id[i][j], v;
            for (int k = 0; k < 6; ++ k) {
                int x = i + dx[k], y = j + dy[k];
                if (!fit(x, y) || !island(d[x][y])) continue;
                v = id[x][y]; if (v == u) continue;
                G[u].push_back(v); G[v].push_back(u);
            }
        }
    }
    for (int i = 0; i < N; ++ i) {
        sort(G[i].begin(), G[i].end());
        G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end());
    }
}

inline bool update(int &a, int b) {
    if (a == -1 || a > b) {a = b; return true;}
    return false;
}

void steiner() {
    for (int msk = 0; msk < 16; ++ msk) {
        for (int u = 0; u < N; ++ u) {
            for (int i = 0; i < (int)G[u].size(); ++ i) {
                int v = G[u][i];
                for (int sub = (msk - 1) & msk; sub; sub = (sub - 1) & msk) {
                    if (~dp[sub][v] && ~dp[msk ^ sub][u]) {
                        update(dp[msk][u], dp[sub][v] + dp[msk ^ sub][u]);
                    }
                }
            }
        }
        queue<int> Q;
        for (int u = 0; u < N; ++ u) {
            if (~dp[msk][u]) Q.push(u), vis[u] = true;
        }
        while (!Q.empty()) {
            int u = Q.front(); Q.pop(); vis[u] = false;
            for (int i = 0; i < (int)G[u].size(); ++ i) {
                int v = G[u][i];
                if (update(dp[msk][v], dp[msk][u] + cost[v]) && !vis[v]) {
                    Q.push(v); vis[v] = true;
                }
            }
        }
    }
}

int solve() {
    memset(vis, 0, sizeof(vis));
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; ++ i) {
        cost[i] = (i >= 4);
        if (i < 4) dp[1 << i][i] = 0;
        else dp[0][i] = 1;
    }
    build(); steiner();
    int ret = -1;
    for (int i = 0; i < N; ++ i) {
        update(ret, dp[15][i]);
    }
    return ret;
}

int main() {
    while (scanf("%d", &R) == 1 && R) {
        while (1) {
            char c = getchar();
            if (c == '\n') break;
        }
        memset(d, 0, sizeof(d));
        memset(id, -1, sizeof(id));
        C = R * 5; R = R * 2 - 1; N = 4;
        for (int i = 1; i <= R; ++ i) gets(d[i] + 1);
        for (int i = 1; i <= R; ++ i) {
            for (int j = 0; j <= C; ++ j) {
                if (!ok(d[i][j]) || ~id[i][j]) continue;
                bfs(i, j, d[i][j]);
            }
        }
        for (int i = 1; i <= R; ++ i) {
            for (int j = 0; j <= C; ++ j) {
                if (d[i][j] == '.') id[i][j] = N ++;
            }
        }
        printf("You have to buy %d parcels.\n", solve());
    }
    return 0;
}

• Relative Posts