Natjecanje 题解：随机化爬山“骗分”实战

前言

本题是 COCI 2025/2026 #2 的一道题目，考察了在网格图上的路径规划与匹配问题。虽然正解涉及复杂的带花树算法，但在特定数据范围内，随机化算法往往能取得意想不到的效果。

1. 题目简述

在一个 \(N \times M\) 的网格图中，有一个中转站 \(S\) 和 \(K\) 个包裹 \(X\)。 每次最多携带两个包裹，从 \(S\) 出发，将所有包裹送到指定位置并返回 \(S\)。 求最短的总时间。

数据范围：\(N, M \le 500\)，\(K \le 67\)。

2. 思路分析

2.1 预处理距离

首先，这是一个网格图上的最短路问题。由于边权都是 1，我们可以使用 BFS 求出任意两点之间的最短距离。 我们需要求出：

  • \(S\) 到任意包裹 \(X_i\) 的距离，记为 \(dist(S, X_i)\)。
  • 任意两个包裹 \(X_i, X_j\) 之间的距离，记为 \(dist(X_i, X_j)\)。

这一步的时间复杂度是 \(O(K \cdot N \cdot M)\)，对于 \(K=67\) 完全可以接受。

2.2 转化为匹配问题

如果不考虑“顺路带两个”，每次只送一个包裹，那么送第 \(i\) 个包裹的代价是 \(2 \times dist(S, X_i)\)（去程+回程）。

如果我们将包裹 \(i\) 和包裹 \(j\) 放在一趟送，路径是 \(S \to X_i \to X_j \to S\)（或者反过来），代价是 \(dist(S, X_i) + dist(X_i, X_j) + dist(X_j, S)\)。

相比于单独送这两个包裹，合并配送节省的时间为： \[ \text{Saving}(i, j) = (2 \times dist(S, X_i) + 2 \times dist(S, X_j)) - (dist(S, X_i) + dist(X_i, X_j) + dist(X_j, S)) \] 化简得： \[ \text{Saving}(i, j) = dist(S, X_i) + dist(S, X_j) - dist(X_i, X_j) \]

我们的目标是总时间最小，等价于节省的时间最大。 问题就转化为了：在 \(K\) 个点中，选出若干对 \((i, j)\) 进行匹配，使得 \(\sum \text{Saving}(i, j)\) 最大。

这是一个经典的一般图最大权匹配问题。

2.3 正解 vs 骗分

  • 正解：一般图最大权匹配通常需要使用带花树算法 (Blossom Algorithm)。但是这个算法极其复杂，考场上很难写对，而且代码量巨大。
  • 骗分技巧：观察数据范围 \(K \le 67\)，这个规模虽然不能用状压 DP，但对于随机化算法来说是一个非常暧昧的范围。我们可以使用随机化爬山 (Randomized Hill Climbing) 或者 模拟退火 (Simulated Annealing) 来寻找近似最优解。

3. 核心技巧：随机化爬山 (Randomized Hill Climbing)

既然我们要把 \(K\) 个物品两两配对，我们可以把它们看作一个排列 \(P\)。

  • \(P_0\) 和 \(P_1\) 配对
  • \(P_2\) 和 \(P_3\) 配对
  • …
  • 如果 \(K\) 是奇数，最后一个落单（不节省时间）。

3.1 算法流程

  1. 初始状态：生成一个随机排列 \(P\)。
  2. 局部优化（爬山）：
    • 尝试交换排列中的任意两个元素 \(P_i, P_j\)。
    • 计算交换后的总节省量 new_saving。
    • 如果 new_saving > current_saving，说明这个交换更优，保留交换并更新当前解。
    • 否则，撤销交换。
    • 重复上述过程，直到无法通过交换任意两个元素来获得更优解（陷入局部最优）。
  3. 随机重启：
    • 为了防止陷入局部最优解，我们在允许的时间内（比如 0.9秒），多次随机打乱序列，重新开始爬山过程。
    • 记录所有轮次中的最大值。

3.2 代码实现细节

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
// 预处理部分省略...
// p[] 存储当前的排列
// calc() 函数计算当前排列 p 下的配对总收益

long long max_saving = 0;
// 卡时技巧：利用 clock() 函数控制运行时间
double start_time = (double)clock() / CLOCKS_PER_SEC;

// 只要时间没超过 0.9s，就一直跑
while ((double)clock() / CLOCKS_PER_SEC - start_time < 0.9) {
    // 1. 随机重启：打乱排列
    random_shuffle(p, p + k);
    long long cur_saving = calc();
    
    // 2. 爬山过程
    while (true) {
        bool improved = false;
        // 尝试交换任意两个位置
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < k; j++) {
                swap(p[i], p[j]); // 尝试交换
                long long new_saving = calc();
                
                if (new_saving > cur_saving) {
                    // 发现更优解，贪心接受
                    cur_saving = new_saving;
                    improved = true;
                } else {
                    // 否则还原
                    swap(p[i], p[j]);
                }
            }
        }
        // 如果这一轮遍历没有任何交换能优化结果，说明到达局部最优，退出当前爬山
        if (!improved) break;
    }
    // 更新全局最优解
    max_saving = max(max_saving, cur_saving);
}

4. 为什么能过？

  1. 状态空间结构：匹配问题的解空间通常比较“平滑”，局部最优解往往离全局最优解不远。
  2. 规模适中：\(K=67\) 意味着 \(O(K^2)\) 的交换尝试非常快。在 1 秒内，我们可以进行成千上万次完整的爬山过程。
  3. 覆盖率高：通过大量的随机重启，大概率能撞到全局最优解。

5. 总结

在 OI 比赛中，遇到“最大权匹配”或者复杂的组合优化问题，如果正解（如带花树、网络流）难以实现，随机化 + 贪心/爬山/退火 往往是性价比最高的策略。

记住这个模板：

  1. while (clock() < limit) 卡时。
  2. random_shuffle 随机重启。
  3. swap + check 局部贪心优化。

这套组合拳在 \(N\) 较小（\(N < 100\)）的非精确覆盖类问题中有着惊人的杀伤力。

6. 完整代码

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
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
char g[505][505];
struct P{int x,y;}s,t[70];
int w[70][70],sd[70];
int dis[505][505];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int p[70];

// BFS 求最短路
void bfs(P o,bool f,int id){
	memset(dis,-1,sizeof(dis));
	queue<P>q;
	q.push(o);
	dis[o.x][o.y]=0;
	while(!q.empty()){
		P u=q.front();q.pop();
		for(int i=0;i<4;i++){
			int x=u.x+dx[i],y=u.y+dy[i];
			if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!='#'&&dis[x][y]==-1){
				dis[x][y]=dis[u.x][u.y]+1;
				q.push((P){x,y});
			}
		}
	}
	if(f){ // 如果是起点 S
		for(int i=0;i<k;i++){
			if(dis[t[i].x][t[i].y]==-1){
				cout<<-1;
				exit(0);
			}
			sd[i]=dis[t[i].x][t[i].y];
		}
	}else{ // 如果是包裹点 X
		for(int i=0;i<k;i++){
			w[id][i]=dis[t[i].x][t[i].y];
		}
	}
}

// 计算当前排列 p 的节省值
long long calc(){
	long long ret=0;
	for(int i=0;i+1<k;i+=2){
		int u=p[i],v=p[i+1];
		ret+=(long long)sd[u]+sd[v]-w[u][v];
	}
	return ret;
}

int main(){
	srand(time(0));
	cin>>n>>m>>k;
	int c=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='S')s=(P){i,j};
			else if(g[i][j]=='X')t[c++]=(P){i,j};
		}
	}
	
	// 预处理距离
	bfs(s,1,-1);
	for(int i=0;i<k;i++)bfs(t[i],0,i);
	
	long long tot=0,ans=0;
	// 基础代价：每个包裹单独送
	for(int i=0;i<k;i++)tot+=2LL*sd[i],p[i]=i;
	
	// 随机化爬山
	double T=(double)clock()/CLOCKS_PER_SEC;
	while((double)clock()/CLOCKS_PER_SEC-T<0.9){ // 卡时 0.9s
		random_shuffle(p,p+k);
		long long cur=calc();
		while(1){
			bool ok=0;
			for(int i=0;i<k;i++){
				for(int j=i+1;j<k;j++){
					swap(p[i],p[j]);
					long long nw=calc();
					if(nw>cur)cur=nw,ok=1;
					else swap(p[i],p[j]); // 没变好就换回来
				}
			}
			if(!ok)break;
		}
		ans=max(ans,cur);
	}
	cout<<tot-ans;
	return 0;
}

随机化算法是 OI 赛场上的奇兵，掌握它，你就能在绝境中找到生机。