题解：火星宝藏探索 - 最小机器人路径覆盖问题

解题思路

本题需要求解在有向无环图（DAG）中覆盖所有顶点所需的最少路径数，即最小路径覆盖问题。根据图论知识，可以将此问题转化为二分图最大匹配问题：

1. 问题转化：将原DAG中的每个顶点$v$拆分为两个顶点$v_{in}$和$v_{out}$，构建二分图
2. 关键定理：最小路径覆盖数 = 顶点数$N$ - 二分图最大匹配数
3. 算法选择：使用Floyd算法计算传递闭包，再用匈牙利算法求最大匹配

算法分析

1. 图的性质：

   • 有向无环图（DAG），边表示单向可达关系
   • 需要找到最少的路径，使得每个顶点至少被一条路径覆盖

2. 复杂度分析：

   • Floyd算法：$O(N^3)$
   • 匈牙利算法：$O(N^2)$
   • 总复杂度：$O(N^3)$ （对于$N \leq 500$可接受）

3. 优化点：

   • 使用邻接矩阵存储图结构
   • 提前终止不必要的循环（代码中的$break$）

实现步骤

1. 问题转化：将“最少机器人数”转化为DAG的最小路径覆盖问题，其值 = 总节点数 - 对应二分图的最大匹配数。
2. 数据初始化：重置邻接矩阵、匹配数组等，初始化原始图的边信息。
3. 传递闭包计算：用Floyd算法补充所有间接可达路径（若i→k且k→j，则i→j）。
4. 最大匹配求解：用匈牙利算法（DFS找增广路径）计算二分图的最大匹配数。
5. 结果计算：按公式“总节点数 - 最大匹配数”输出最少机器人数。

C++代码实现（带详细注释）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;

// 定义常量：最大顶点数（题目中N≤500，这里设为1005留有余地）
const int maxx=1005;
// 定义无穷大值，用于初始化距离矩阵
const int inf=0x3f3f3f3f;

// 匈牙利算法中的访问标记数组（标记节点是否被访问过）
int used[maxx];
// 邻接矩阵line[i][j]：表示i到j是否有直接或间接的路径（传递闭包结果）
int line[maxx][maxx];
// 未使用的标记数组（可能是历史遗留，当前代码中未实际使用）
int vis[maxx];
// 图的顶点数n和边数m
int n,m;
// 邻接矩阵e[i][j]：存储原始图的直接边（1表示有边，inf表示无边）
int e[maxx][maxx];
// 匹配数组nxt[j] = i：表示在二分图匹配中，j匹配到i
int nxt[maxx];

// 初始化函数：重置所有数组的状态
void init(){
    memset(used,0,sizeof(used));   // 重置访问标记数组
    memset(vis,0,sizeof(vis));     // 重置未使用的标记数组
    memset(line,0,sizeof(line));   // 重置传递闭包矩阵
    memset(nxt,-1,sizeof(nxt));    // 重置匹配数组（-1表示未匹配）
    
    // 初始化原始图邻接矩阵e
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                e[i][j]=0;  // 节点到自身的距离为0
            }else{
                e[i][j]=inf;  // 初始时节点间无直接边，设为inf
            }
        }	
    }
}

// Floyd算法：计算图的传递闭包
// 传递闭包的含义：如果i到k有路径且k到j有路径，则i到j有路径
void floyd(int n){
    // 枚举中间节点k
    for(int k=1;k<=n;k++){
        // 枚举起点i
        for(int i=1;i<=n;i++){
            // 枚举终点j
            for(int j=1;j<=n;j++){
                // 如果i到k有直接边，且k到j有直接边，则i到j有间接边
                if(e[i][k]==1&&e[k][j]==1){
                    line[i][j]=1;  // 标记i到j有路径
                }
            }
        }
    }
}

// 深度优先搜索（DFS）：用于匈牙利算法寻找增广路径
// 参数x：当前需要匹配的左部节点
// 返回值：是否能为x找到匹配的右部节点
int Find(int x){
    // 枚举所有可能的右部节点i
    for(int i=1;i<=n;i++){
        // 如果i未被访问，且x到i有路径（line[x][i]==1）
        if(used[i]==0&&line[x][i]==1){
            used[i]=1;  // 标记i为已访问，避免重复匹配
            // 如果i未被匹配（nxt[i]==-1），或i的当前匹配节点可以找到其他匹配
            if(nxt[i]==-1||Find(nxt[i])){
                nxt[i]=x;  // 将i匹配给x
                return true;  // 匹配成功
            }
        }
    }
    return false;  // 匹配失败
}

// 匈牙利算法：计算二分图的最大匹配数
int match(){
    int sum=0;  // 记录匹配数
    // 枚举所有左部节点（这里将所有节点视为左部）
    for(int i=1;i<=n;i++){
        memset(used,0,sizeof(used));  // 每次匹配前重置访问标记
        if(Find(i)){  // 如果能为i找到匹配
            sum++;  // 匹配数加1
        }
    }
    return sum;  // 返回最大匹配数
}

int main(){
    int t;  // 未使用的变量（可能是历史遗留）
    // 循环读取测试用例，直到输入0 0结束
    while(scanf("%d %d",&n,&m)){
        if(n==0&&m==0)break;  // 终止条件
        
        init();  // 初始化数组
        
        // 读取m条边
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            e[a][b]=1;  // 标记原始图中a到b有直接边
            line[a][b]=1;  // 初始时传递闭包矩阵先记录直接边
        }
        
        // 计算传递闭包：补充所有间接可达的路径
        floyd(n);
        
        // 计算二分图最大匹配数
        int ans=match();
        
        // 最少机器人数 = 总节点数 - 最大匹配数（DAG最小路径覆盖定理）
        cout<<n-ans<<endl;
    } 
    return 0;
}

复杂度分析

1. 时间复杂度：

   • Floyd算法计算传递闭包：$O(N^3)$
   • 匈牙利算法求最大匹配：$O(N^2)$
   • 总时间复杂度：$O(N^3)$

2. 空间复杂度：

   • 邻接矩阵存储：$O(N^2)$
   • 辅助数组：$O(N)$