[KMOI R1] 军事行动

GitHub 跳转原题关系图返回列表

先用 BFS 求出任意两座城市之间的最短骑士步数，再把“从已占领城市攻占一座新城市”的代价视作边权，整道题就转化成一棵最小生成树。

OJ: luogu

题目 ID: P9709

难度:提高+/省选-

标签:图论最小生成树bfs

日期: 2026-06-20 01:11

题意

有 n 座城市，城市 1 一开始就已经被占领。

之后每次只能做一件事：

从某个已经占领的城市派出一支舰队去攻打一座还没占领的城市

舰队在棋盘上按“日”移动，移动方式和国际象棋里的马一样：

(+/-1, +/-2)
(+/-2, +/-1)

并且坐标必须始终留在 1..m 的方形区域内。

舰队到达目标城市后，要到第二天这座城市才算被攻占。

问最少多少天能攻占所有城市。

样例一过程表

这张表展示样例一中唯一一支舰队的行动过程：

天数结束后	状态
第 1 天	舰队从 `(1,1)` 走到 `(3,2)`
第 2 天	舰队从 `(3,2)` 走到 `(1,3)`
第 3 天	城市 `2` 被攻占

所以答案是 3。

思路

先看一个只适合很小数据的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112// brute.cpp：小图状压 DP，直接按“占领集合”转移。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const int MAXM = 20;
const int INF = 1e9;

int n, board_size;
int x[MAXN], y[MAXN];
int board_dist[MAXM][MAXM];
int city_dist[MAXN][MAXN];
int dp[1 << MAXN];
int dx[8] = {-1, 1, 2, -2, -1, 1, 2, -2};
int dy[8] = {2, 2, 1, 1, -2, -2, -1, -1};

void bfs_from(int start_id) {
    for (int i = 1; i <= board_size; i++) {
        for (int j = 1; j <= board_size; j++) {
            board_dist[i][j] = -1;
        }
    }

    queue<pair<int, int>> q;
    q.push({x[start_id], y[start_id]});
    board_dist[x[start_id]][y[start_id]] = 0;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int cx = cur.first;
        int cy = cur.second;

        for (int i = 0; i < 8; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx <= 0 || ny <= 0 || nx > board_size || ny > board_size) {
                continue;
            }
            if (board_dist[nx][ny] != -1) {
                continue;
            }

            board_dist[nx][ny] = board_dist[cx][cy] + 1;
            q.push({nx, ny});
        }
    }

    for (int i = 1; i <= n; i++) {
        city_dist[start_id][i] = board_dist[x[i]][y[i]];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> board_size;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    for (int i = 1; i <= n; i++) {
        bfs_from(i);
    }

    int max_mask = 1 << n;
    for (int i = 0; i < max_mask; i++) {
        dp[i] = INF;
    }
    dp[1 << 0] = 0;

    for (int mask = 0; mask < max_mask; mask++) {
        if (dp[mask] == INF) {
            continue;
        }

        for (int j = 1; j <= n; j++) {
            if ((mask >> (j - 1)) & 1) {
                continue;
            }

            int best = INF;
            for (int i = 1; i <= n; i++) {
                if (((mask >> (i - 1)) & 1) == 0) {
                    continue;
                }
                if (city_dist[i][j] == -1) {
                    continue;
                }
                best = min(best, city_dist[i][j] + 1);
            }

            if (best == INF) {
                continue;
            }

            int next_mask = mask | (1 << (j - 1));
            dp[next_mask] = min(dp[next_mask], dp[mask] + best);
        }
    }

    if (dp[max_mask - 1] == INF) {
        cout << -1 << '\n';
    } else {
        cout << dp[max_mask - 1] << '\n';
    }

    return 0;
}

暴力直接做状压 DP：

mask 表示哪些城市已经被占领
下一步可以从 mask 里的任意城市出发，去攻打一座还没占领的城市

这个模型非常贴题，但 n = 2000 时不可能再做状态压缩。

关键观察有两层。

第一层：如果一座新城市 v 是从已占领城市 u 出发攻占的，那么这次操作的代价只取决于两城之间的最短骑士步数：

走到 v 要 dist(u,v) 天
到达后的第二天才攻占，所以总共还要再 +1

也就是说，u -> v 的代价是：

dist(u,v) + 1

第二层：因为题目明确说，在一支舰队前往攻打或正在攻打某座城市时，不能再派出别的舰队，所以整个攻占过程一定是串行的。

于是，任意一种攻占方案都可以看成一棵以城市 1 为根的树：

每个非根城市只会被第一次攻占一次
它一定有一个“父城市”，表示是从哪座已占领城市出发攻下它的

这棵树上的每条边 (u,v) 都贡献 dist(u,v)+1 的代价，总答案就是所有边权之和。

所以问题已经变成：

在 n 个城市之间建立一张完全图，边权是 dist(u,v)+1，求从城市 1 出发覆盖所有城市的最小总代价。

由于边权是对称的，这其实就是最小生成树。

于是做法分两步：

先 BFS 求出城市两两之间的最短骑士步数
再在这些城市上做一棵 MST

点数是 2000，棋盘边长最多 150，所以主解可以写成：

每次 Prim 选中一个新城市 u
就从 u 做一遍 BFS，更新它到所有未占领城市的边权 dist(u,v)+1

这样既不用预存所有边，也不用预存完整的城市两两距离矩阵。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
const int MAXM = 155;
const int INF = 1e9;

int n, board_size;
int x[MAXN], y[MAXN];
int dist_to_tree[MAXN];
bool vis[MAXN];
int board_dist[MAXM][MAXM];
int dx[8] = {-1, 1, 2, -2, -1, 1, 2, -2};
int dy[8] = {2, 2, 1, 1, -2, -2, -1, -1};

void bfs_from(int start_id) {
    for (int i = 1; i <= board_size; i++) {
        for (int j = 1; j <= board_size; j++) {
            board_dist[i][j] = -1;
        }
    }

    queue<pair<int, int>> q;
    q.push({x[start_id], y[start_id]});
    board_dist[x[start_id]][y[start_id]] = 0;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int cx = cur.first;
        int cy = cur.second;

        for (int i = 0; i < 8; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx <= 0 || ny <= 0 || nx > board_size || ny > board_size) {
                continue;
            }
            if (board_dist[nx][ny] != -1) {
                continue;
            }

            board_dist[nx][ny] = board_dist[cx][cy] + 1;
            q.push({nx, ny});
        }
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            continue;
        }
        int step = board_dist[x[i]][y[i]];
        if (step == -1) {
            continue;
        }
        dist_to_tree[i] = min(dist_to_tree[i], step + 1);
    }
}

int prim() {
    for (int i = 1; i <= n; i++) {
        dist_to_tree[i] = INF;
        vis[i] = false;
    }

    dist_to_tree[1] = 0;
    int answer = 0;

    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (vis[j]) {
                continue;
            }
            if (u == 0 || dist_to_tree[j] < dist_to_tree[u]) {
                u = j;
            }
        }

        if (u == 0 || dist_to_tree[u] == INF) {
            return -1;
        }

        vis[u] = true;
        answer += dist_to_tree[u];
        bfs_from(u);
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> board_size;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    cout << prim() << '\n';

    return 0;
}

复杂度

设城市数为 n，棋盘边长为 m。

Prim 一共会选出 n 个城市；每选出一个城市，就做一次棋盘 BFS：

一次 BFS 是 $O(m^2)$
外层 Prim 选点和更新城市代价总共是 $O(n^2)$

所以总复杂度可以写成：

$O(n m^2 + n^2)$

在本题数据范围内是可以接受的。

总结

这题最关键的一步，是把“攻占顺序”看成一棵树。只要意识到整个过程不能并行，总代价就是若干次“从已占领城市接入一座新城市”的和，于是题目自然转化成了“BFS 求边权 + 最小生成树”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P9709 [KMOI R1] 军事行动

题目背景

\blue{他们来了。}

\purple{集结军队，干掉他们，一个不留。}

\blue{是！}

题目描述

喵星边境局势愈发紧张，导致发生边境冲突。喵星军队总司令小袁立即对 $Y$ 星采取军事行动。

整个宇宙可以看作一个平面直角坐标系，城市 $1,2,\dots,n$ 的坐标分别为 $(x_1,y_1),(x_2,y_2),\dots(x_n,y_n)$ 。

现在小袁率领的若干支舰队（可以理解为小袁的军事力量是无限的）驻扎在边境要塞，城市 $1$ 处。他的舰队会进行以下移动：

如果舰队的坐标为 $(x,y)$ ，那么一天之后它可以移动到 $(x-1,y+2)$ 或 $(x+1,y+2)$ 或 $(x+2,y+1)$ 或 $(x-2,y+1)$ 或 $(x-1,y-2)$ 或 $(x+1,y-2)$ 或 $(x+2,y-1)$ 或 $(x-2,y-1)$ 处。

其中环绕在外的还有一条小行星带，当舰队的坐标 $(x,y)$ 且 $x\le 0$ 或 $y\le 0$ 或 $m < x$ 或 $m < y$ 时，舰队就会撞到小行星带。这是小袁所不想看到的。

现在小袁要攻打城市 $2,3,\dots,n$ ，每一次他都会从一个已经占领的城市（城市 $1$ 也算），派出舰队前往城市 $i$ 并攻打它，舰队到达之后的第二天城市 $i$ 就被攻占了。

特别的，小袁在一个舰队前往攻打或攻打一个城市的时候不会派出另外一支舰队，在攻占一座城市后当天可以立即派出另外一支舰队。

小袁想问，最少要花多少时间才能攻占所有的城市。

攻打顺序可以不按照 $2,3\dots n$ 的顺序。

输入格式

第一行一个整数 $n,m$ ，表示城市个数和小行星带的范围。

接下来 $n$ 行，每一行两个正整数 $(x_i,y_i)$ ，表示城市 $i$ 的坐标。保证 $1\le x_i,y_i \le m$ 。

输出格式

一个整数 $ans$ ，表示最少要花的时间。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

输入输出样例 #4

输入 #4

text

1查看附件的 example4.in

输出 #4

text

1查看附件的 example4.out

说明/提示

样例一解释：

舰队在第一天来到了 $(3,2)$ 的位置，第二天到达了城市 $2$ 的位置，第三天占领了城市 $2$ 。总共花了 $3$ 天。

样例二解释：

舰队在第一天到达了城市 $2$ 的位置，第二天占领了城市 $2$ 。第三天到达了城市 $3$ 的位置，第四天占领了城市 $3$ 。总共花了 $4$ 天。

数据范围

本题采用 Subtask 捆绑测试。

子任务编号	测试点编号	$n$	$m$	特殊性质	分值
$1$	$1\sim2$	$1\le n\le 7$	$4\le m\le 7$	无	$10$
$2$	$3\sim7$	$1\le n\le 200$	$4\le m\le 70$	无	$25$
$3$	$8\sim9$	$1\le n\le 150$	$4\le m\le 150$	有	$15$
$4$	$10\sim20$	$1\le n\le 2000$	$4\le m\le 150$	无	$50$

特殊性质：对于每一个 $1\le i\le n-1$ ，都有 $x_i = x_{i+1}$ 。

数据严格保证不会有不同的城市拥有相同的坐标。

[KMOI R1] 军事行动

目录

题意

样例一过程表

思路

代码

复杂度

总结

一图流解析