题解：P13174 [GCJ 2017 #2] Shoot the Turrets

水星湖 · 2026-04-23 21:53:23 · 题解

这个做法应该比官方题解麻烦点。

忽略所有炮台的限制，求出每个士兵在不超过限制的距离的情况下能与哪些炮台处于同一行或列。在这样的士兵和炮台之间连边得到二分图 G。答案就是这个二分图的最大匹配。不会证。

考虑怎么构造方案，可以 O(n^3) 求出哪些士兵炮台的点对在此时是合法的。每个合法点对都一定对应 G 中的一条边 e。如果这一步操作可以选择这一对点，当且仅当这个 G 中存在包含 e 的最大匹配。找到合法的 e 之后，可以直接在 G 中把两个 e 的端点删掉。

问题是如何判断每条边是否在某个最大匹配中。首先求出一个最大匹配，然后将最大匹配内的边反向得到图 G'，再将 G' 反向得到 G''，那么 (u,v) 在 G 的某个最大匹配中当且仅当满足以下三个条件之一：

这样可以做到 O(n^4)。据说能过。

可以进一步优化。首先最大匹配不需要每次重新求，注意到删掉两个点之后此时原来的最大匹配大小至多减少 2，只需要增广一次就能得到最大匹配，这样就可以 O(n^2) 求出新的最大匹配。bfs 的总复杂度还是 O(n^4) 的。有一个显然的性质是合法的士兵炮台点对是不会变少的。bfs 的起点可以选择上次删除炮台之后可以继续移动的点。这个士兵新的能到达的点能攻击到的新的炮台与这个士兵形成一些新的合法的点对。预处理每个位置能攻击到哪些炮台。这样对于每个士兵而言，每个位置都只会访问 O(1) 次，每个炮台会被每个士兵能到达的点在新加合法点对的过程中访问 O(n) 次。因此均摊的复杂度就是对的。可能需要用 dijkstra，精细实现也许可以做到 O(n^3)，但是常数巨大，第二组数据很难跑进 1s/ll

放个 O(n^3\log n) 的代码。

::::info[code]

#include <bits/stdc++.h>
using namespace std;

namespace z {

const int N = 200 + 5;
int R, C, n, m, lim, dis[N][N][N], a[N][N];
pair<int, int> pos[N];
vector<int> p[N], g[N], gr[N];
int vis[N], match[N], used[N];
int cnt[N][N], reachl[N], reachr[N];
vector<int> see[N][N];
bool dfs(int u) {
    if(used[u]) return false;
    for(int v : p[u]) if(!vis[v] && !used[v]) {
        vis[v] = 1;
        if(!match[v] || dfs(match[v])) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
void bfs(int x, int y, int (&dis)[N][N]) {
    queue<array<int, 3>> q;
    q.push({x, y, 0});
    dis[x][y] = 0;
    while(!q.empty()) {
        auto [x, y, d] = q.front(); q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > R || ny < 1 || ny > C) continue;
            if(a[nx][ny] == 1) continue;
            if(dis[nx][ny] > d + 1) {
                dis[nx][ny] = d + 1;
                q.push({nx, ny, d + 1});
            }
        }
    }
}
int low[N], dfn[N], cdfn, stk[N], ins[N], top, id[N], scc;
void tarjan(int u) {
    low[u] = dfn[u] = ++cdfn;
    stk[++top] = u;
    ins[u] = 1;
    for(int v : g[u]) {
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(ins[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        int v; ++scc;
        do {
            v = stk[top--];
            ins[v] = 0;
            id[v] = scc;
        } while(v != u);
    }
}
void dfsl(int u) {
    reachl[u] = 1;
    for(int v : g[u]) if(!reachl[v]) dfsl(v);
}
void dfsr(int u) {
    reachr[u] = 1;
    for(int v : gr[u]) if(!reachr[v]) dfsr(v);
}
void cal() {
    cdfn = scc = 0;
    memset(dfn, 0, sizeof(dfn));
    for(int i = 1; i <= n + m; i++) if(!dfn[i]) tarjan(i);
    set<int> st; 
    memset(reachl, 0, sizeof(reachl));
    memset(reachr, 0, sizeof(reachr));
    for(int i = 1; i <= m; i++) st.insert(match[n + i]);
    for(int i = 1; i <= n; i++) if(!st.count(i)) dfsl(i);
    for(int i = 1; i <= n + m; i++) gr[i].clear();
    for(int i = 1; i <= n + m; i++) for(int j : g[i]) gr[j].push_back(i);
    for(int i = 1; i <= m; i++) if(!match[n + i]) dfsr(n + i);
}
void solve() {
    cin >> C >> R >> lim;
    n = m = 0;
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= R; i++) {
        string str; cin >> str;
        for(int j = 1; j <= C; j++) {
            if(str[j - 1] == '.') a[i][j] = 0;
            if(str[j - 1] == '#') a[i][j] = 1;
            if(str[j - 1] == 'S') a[i][j] = 2;
            if(str[j - 1] == 'T') a[i][j] = 3; 
            see[i][j].clear(); cnt[i][j] = 0;
        }
    }
    for(int i = 1; i <= R; i++)
        for(int j = 1; j <= C; j++)
            if(a[i][j] == 2) pos[++n] = {i, j};
    for(int i = 1; i <= R; i++)
        for(int j = 1; j <= C; j++)
            if(a[i][j] == 3) {
                pos[n + (++m)] = {i, j};
                for(int k = i; k >= 1; k--) {
                    if(a[k][j] == 1) break;
                    cnt[k][j]++;
                    see[k][j].push_back(n + m);
                }
                for(int k = i; k <= R; k++) {
                    if(a[k][j] == 1) break;
                    cnt[k][j]++;
                    see[k][j].push_back(n + m);
                }
                for(int k = j; k >= 1; k--) {
                    if(a[i][k] == 1) break;
                    cnt[i][k]++;
                    see[i][k].push_back(n + m);
                }
                for(int k = j; k <= C; k++) {
                    if(a[i][k] == 1) break;
                    cnt[i][k]++;
                    see[i][k].push_back(n + m);
                }
                cnt[i][j] -= 3;
            }
    for(int i = 1; i <= n + m; i++) p[i].clear();
    for(int i = 1; i <= n; i++) {
        bfs(pos[i].first, pos[i].second, dis[i]);
        for(int j = 1; j <= m; j++) {
            auto [x, y] = pos[n + j];
            bool flg = 0;
            for(int k = x; k >= 1; k--) {
                if(a[k][y] == 1) break;
                if(dis[i][k][y] <= lim) flg = 1;
            }
            for(int k = x; k <= R; k++) {
                if(a[k][y] == 1) break;
                if(dis[i][k][y] <= lim) flg = 1;
            }
            for(int k = y; k >= 1; k--) {
                if(a[x][k] == 1) break;
                if(dis[i][x][k] <= lim) flg = 1;
            }
            for(int k = y; k <= C; k++) {
                if(a[x][k] == 1) break;
                if(dis[i][x][k] <= lim) flg = 1;
            }
            if(flg) p[i].push_back(n + j);
        }
    }
    memset(match, 0, sizeof(match));
    memset(used, 0, sizeof(used));
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans++;
    }
    cout << ans << '\n';
    set<pair<int, int>> edge;
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= n; i++) dis[i][pos[i].first][pos[i].second] = 0;
    int lst = 0;
    while(ans--) {
        for(int p = 1; p <= n; p++) {
            vector<array<int, 3>> v;
            vector<pair<int, int>> newpos;
            if(lst) {
                int r = pos[lst].first;
                for(int c = 1; c <= C; c++) 
                    if(dis[p][r][c] < 1e9) v.push_back({dis[p][r][c], r, c});
                int c = pos[lst].second;
                for(int r = 1; r <= R; r++) 
                    if(dis[p][r][c] < 1e9) v.push_back({dis[p][r][c], r, c});
            } else {
                v.push_back({0, pos[p].first, pos[p].second});
                newpos.push_back(pos[p]);
            }
            sort(v.begin(), v.end());
            priority_queue<array<int, 3>, vector<array<int, 3>> , greater<array<int, 3>>> q;
            for(auto [d, r, c] : v) q.push({d, r, c});
            while(!q.empty()) {
                auto [d, x, y] = q.top(); q.pop();
                if(d + 1 > lim || cnt[x][y]) continue;
                for(int i = 0; i < 4; i++) {
                    int nx = x + dx[i], ny = y + dy[i];
                    if(nx < 1 || nx > R || ny < 1 || ny > C) continue;
                    if(a[nx][ny] == 1 || a[nx][ny] == 3) continue;
                    if(dis[p][nx][ny] > d + 1) {
                        dis[p][nx][ny] = d + 1;
                        newpos.push_back({nx, ny});
                        q.push({d + 1, nx, ny});
                    }
                }
            }
            for(auto [x, y] : newpos)
                for(int j : see[x][y])
                    edge.insert({p, j});
        }
        for(int i = 1; i <= n + m; i++) g[i].clear();
        for(int i = 1; i <= n; i++) if(!used[i]) {
            for(int j : p[i]) if(!used[j]) {
                if(match[j] != i) g[i].push_back(j);
                else g[j].push_back(i);
            }
        }
        cal();
        for(auto [u, v] : edge) if(!used[u] && !used[v]) {
            if(id[u] == id[v] || reachl[u] || reachr[v] || match[v] == u) {
                used[u] = used[v] = 1;
                match[match[v]] = 0;
                match[match[u]] = 0;
                match[v] = match[u] = 0;
                for(int k = pos[v].first; k >= 1; k--) {
                    if(a[k][pos[v].second] == 1) break;
                    cnt[k][pos[v].second]--;
                }
                for(int k = pos[v].first; k <= R; k++) {
                    if(a[k][pos[v].second] == 1) break;
                    cnt[k][pos[v].second]--;
                }
                for(int k = pos[v].second; k >= 1; k--) {
                    if(a[pos[v].first][k] == 1) break;
                    cnt[pos[v].first][k]--;
                }
                for(int k = pos[v].second; k <= C; k++) {
                    if(a[pos[v].first][k] == 1) break;
                    cnt[pos[v].first][k]--;
                }
                cnt[pos[v].first][pos[v].second] += 3;
                a[pos[v].first][pos[v].second] = 0;
                lst = v;
                cout << u << " " << v - n << '\n';
                memset(vis, 0, sizeof(vis));
                for(int i = 1; i <= n; i++) if(!used[i] && !match[i]) dfs(i);
                break;
            }
        }
    }
}
void main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int T; cin >> T;
    for(int i = 1; i <= T; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
}

#undef int

}

int main()
{
    z::main();
    return 0;
}

::::