题解：机器人清理垃圾问题（Mid-Central USA 2003）

一、题目分析

本题要求计算清理场地垃圾所需的最少机器人数量。机器人从西北角(1,1)出发，只能向东或向南移动，终点为东南角(m,n)。关键条件：

• 机器人路径上的垃圾点需满足行和列非递减（即若机器人经过(r1,c1)，则后续垃圾点(r2,c2)需满足r1≤r2且c1≤c2）
• 目标是用最少机器人覆盖所有垃圾点

二、解题思路

1. 问题转化

最少机器人数量等价于求垃圾点集合的最小链覆盖数。根据Dilworth定理：

一个偏序集的最小链覆盖数等于其最长反链的长度

其中：

• 链：垃圾点序列中任意两点满足(r_i≤r_j且c_i≤c_j)
• 反链：垃圾点序列中任意两点都不满足(r_i≤r_j且c_i≤c_j)

2. 算法选择

通过匈牙利算法计算二分图最大匹配，再利用公式：
[ \text{最小链覆盖数} = \text{点数} - \text{最大匹配数} ]
步骤如下：

1. 将每个垃圾点拆分为二分图左右两部分节点
2. 若垃圾点i和j满足i可被j覆盖（r_i≤r_j且c_i≤c_j），则连边i→j
3. 计算二分图最大匹配，最终结果为点数-最大匹配数

三、代码解析

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 25 * 25;  // 最大垃圾点数（24×24=576）

int x[N], y[N], cnt = 1;  // x/y存储垃圾点坐标，cnt为点数
vector<int> g[N];        // 邻接表存储二分图边

// 判断点i是否可被点j覆盖（j在i的右下方）
bool judge(int i, int j) {
    return x[j] >= x[i] && y[j] >= y[i];
}

int left[N], vis[N];     // left[v]记录右部点v匹配的左部点，vis用于DFS标记

// 二分图匹配的DFS过程
bool dfs(int u) {
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (vis[v]) continue;
        vis[v] = 1;
        // 若v未匹配或v的匹配点可找到新匹配
        if (left[v] == -1 || dfs(left[v])) {
            left[v] = u;
            return true;
        }
    }
    return false;
}

// 匈牙利算法计算最大匹配
int hungary() {
    int ans = 0;
    memset(left, -1, sizeof(left));
    for (int i = 0; i < cnt; i++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(i)) ans++;
    }
    return ans;
}

int main() {
    while (~scanf("%d%d", &x[0], &y[0])) {
        if (x[0] == -1 && y[0] == -1) break;  // 输入结束条件
        
        // 读取当前地图所有垃圾点
        while (~scanf("%d%d", &x[cnt], &y[cnt])) {
            if (x[cnt] == 0 && y[cnt] == 0) break;  // 地图结束标记
            cnt++;
        }
        
        // 构建二分图：若i可被j覆盖，则连边i→j
        for (int i = 0; i < cnt; i++) {
            g[i].clear();
            for (int j = 0; j < i; j++) {
                if (judge(i, j)) g[i].push_back(j);  // i可被j覆盖，连边i→j
                if (judge(j, i)) g[j].push_back(i);  // j可被i覆盖，连边j→i
            }
        }
        
        // 计算最小链覆盖数并输出
        printf("%d\n", cnt - hungary());
        cnt = 1;  // 重置点数计数器
    }
    return 0;
}

四、关键步骤解析

1. 输入处理

   • 读取垃圾点坐标，直到遇到0 0表示当前地图结束，-1 -1表示所有输入结束
   • 坐标存储在x[]和y[]数组中，cnt记录垃圾点数量

2. 图的构建

   • 对于每对垃圾点(i,j)，若j在i的右下方（x[j]≥x[i]且y[j]≥y[i]），则在二分图中添加边i→j
   • 邻接表g[]存储所有可达关系

3. 匈牙利算法

   • 将问题转化为二分图最大匹配问题，left[]数组记录右部点的匹配情况
   • dfs(u)尝试为左部点u寻找增广路径，更新匹配关系

4. 结果计算

   • 最小链覆盖数 = 垃圾点数 - 最大匹配数
   • 该公式基于Dilworth定理和二分图匹配理论

五、示例解析

以输入数据第二个地图为例：
垃圾点为(1,1)、(2,2)、(4,4)

• 构建二分图边：
  (1,1)可被(2,2)和(4,4)覆盖，(2,2)可被(4,4)覆盖
• 最大匹配数为2（例如(1,1)-(2,2)，(2,2)-(4,4)）
• 最小链覆盖数 = 3 - 2 = 1，即只需1个机器人

六、算法优化

1. 排序优化
   可先按行优先排序垃圾点，减少不必要的判断
2. 复杂度分析
   • 时间复杂度：O(n³)，n为垃圾点数（n≤576）
   • 空间复杂度：O(n²)，主要用于邻接表存储

七、注意事项

1. 坐标编号
   题目中行列从1开始编号，与代码中数组索引一致
2. 输入结束条件
   需正确处理0 0（地图结束）和-1 -1（全部输入结束）的区别
3. Dilworth定理应用
   必须确保偏序关系定义正确（本题中为(r_i≤r_j且c_i≤c_j)）