P2172 [国家集训队] 部落战争 题解

· · 题解

题意

有 m\times n 的网格，对于网格上的一点 (i,j)，如果是城市，则需要占领，即必须通过，且只能通过一次；否则，不能通过，无需占领。最少需几个军队？

对于每个军队，其行动范围又两个数据控制 R,C，若现在为 (i,j)，下一步能到 \{(i+R,j+C),(i+R)(j-C),(i+C,j+R),(i+C,j-R)\} 处。

分析

“并只能从上往向下征战，不能回头。”这句话明显在提醒我们，这是一个有向无环图。“假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮 lanzerb 算算至少要多少支军队才能完成统一全国的大业。”题意已经很裸了，是要我们求最少覆盖路径。

具体的，遍历整个网格，枚举每个网格可到达得点，如果两点都是城市，就建一条边，表示可行的一条路径，求出最少覆盖路径。

求解

假设现在每个点都布置一个军队，每个军队都只经过一个点。现在要将一些能合并为一条路径的点合并。对于每个点，只能有一个出度，或是路径的终点；只能有一个入度，或是路径的起点。

将一个点 u\in V 拆成两个点 u_1,u_2。分别表示进入 u；从 u 离开。对于原图中的边 (i,j)\in E，连接 i_1,j_2，表示能够从 i 走出，走向 j，并将两点并为一条路线。因为对于每个点，只能有一个出度，或是路径的终点；只能有一个入度，或是路径的起点。所以路径的合并过程，实际上是二分图最大匹配。

这里建议使用网络流 Dinic 求解。从源点 s 向所有 i_1,i\in V 连一条边，容量为一，表示只能匹配一次；从 i_2,i\in V 向汇点 t 连一条容量为一的边，表示只能被匹配一次。对于一条连边 (i,j)\in E，从 i_1 到 j_2 连一条容量为一的边，表示可以匹配。

最后求出的最大匹配就是能将几个点合并为一条路线，即能省出几个军队。用城市数减匹配数就是答案。

C++ Code

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

class Dinic {
    public:
        typedef int TYPE;
        static const int maxn = (55 * 55) << 1, maxm = 0x7f7f7f7f, inf = 0x7f7f7f7f;
        class edge {
            public:
                int to, rev;
                TYPE flow;
                edge(int to, TYPE flow, int rev): to(to), flow(flow), rev(rev) {}
                edge() {}
        };
        std::vector<edge>vec[maxn];
        int h[maxn], Cur[maxn], n, m, s, t;
        bool vis[maxn], Map[55][55];
        Dinic(int n, int m, int s, int t): n(n), m(m), s(s), t(t),
            h({0}), Cur({0}), vis({false}) {}
        Dinic() {}
        inline void Add_Edge(int from, int to, TYPE flow) {
            vec[from].push_back(edge(to, flow, vec[to].size()));
            vec[to].push_back(edge(from, 0, vec[from].size() - 1));
        }
        inline bool bfs() {
            int q[maxn], front = 0, back = -1;
            std::memset(q, 0, sizeof(q));
            std::memset(h, inf, sizeof(h));
            h[t] = 0;
            std::memset(Cur, 0, sizeof(Cur));
            for (q[++back] = t; front <= back;) {
                int u = q[front++];
                for (edge &e : vec[u]) {
                    int v = (e.to);
                    if (vec[v][e.rev].flow && h[v] == inf) {
                        h[v] = h[u] + 1;
                        q[++back] = v;
                    }
                }
            }
            return h[s] != inf;
        }
        inline TYPE dfs(int u, TYPE flow) {
            if (u == t || !flow) {
                return flow;
            }
            TYPE res = 0;
            vis[u] = true;
            int sz = vec[u].size();
            for (int i = Cur[u]; i < sz && flow; ++i) {
                edge &e = vec[u][i];
                int v = (e.to);
                if (e.flow && h[v] + 1 == h[u] && !vis[v]) {
                    TYPE Preflow = dfs(v, std::min(flow, e.flow));
                    e.flow -= Preflow, vec[v][e.rev].flow += Preflow;
                    res += Preflow, flow -= Preflow;
                }
            }
            vis[u] = false;
            return res;
        }
        inline TYPE GetMaxFlow() {
            TYPE MaxFlow = 0;
            while (bfs()) {
                TYPE GetFlow;
                while ((GetFlow = dfs(s, inf))) {
                    MaxFlow += GetFlow;
                }
            }
            return MaxFlow;
        }
        inline void InPut(int &NodeNum, int &Cnt) {
#define id(a,b) ((a-1)*M+b)
            Cnt = 0;
            int N, M, R, C;
            scanf("%d%d%d%d", &N, &M, &R, &C);
            this[0] = Dinic(((N * M) << 1) + 2, M, 0, ((N * M) << 1) + 1);
            int nex[4][2] = {{R, C}, {R, -C}, {C, R}, {C, -R}};
            NodeNum = N * M;
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= M; ++j) {
                    char tmp;
                    std::cin >> tmp;
                    if (tmp == 'x') {
                        Map[i][j] = false;
                    } else {
                        Map[i][j] = true;
                        ++Cnt;
                    }
                }
            }
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= M; ++j) {
                    if (Map[i][j]) {
                        for (int k = 0; k < 4; ++k) {
                            int X = i + nex[k][0], Y = j + nex[k][1];
                            if (X >= 1 && X <= N && Y >= 1 && Y <= M) {
                                if (Map[X][Y]) {
                                    Add_Edge(id(i, j), id(X, Y) + NodeNum, 1);
                                }
                            }
                        }
                    }
                }
            }
            for (int i = 1; i <= NodeNum; ++i) {
                Add_Edge(s, i, 1);
                Add_Edge(i + NodeNum, t, 1);
            }
        }
        inline void Solve() {
            int NodeNum, Cnt;
            InPut(NodeNum, Cnt);
            int MaxFlow = GetMaxFlow();
            printf("%d\n", Cnt - MaxFlow);
        }
};
Dinic Main;

int main() {
    Main.Solve();
    return 0;
}