本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：379. 捉迷藏 - AcWing题库
【题目描述】
Vani 和 cl2 在一片树林里捉迷藏。
这片树林里有N NN座房子，M MM条有向道路，组成了一张有向无环图。
树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。
如果从房子A AA沿着路走下去能够到达B BB，那么在A AA和B BB里的人是能够相互望见的。
现在 cl2 要在这N NN座房子里选择K KK座作为藏身点，同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找，为了避免被 Vani 看见，cl2 要求这K KK个藏身点的任意两个之间都没有路径相连。
为了让 Vani 更难找到自己，cl2 想知道最多能选出多少个藏身点。
【输入】
输入数据的第一行是两个整数N NN和M MM。
接下来M MM行，每行两个整数x , y x,yx,y，表示一条从x xx到y yy的有向道路。
【输出】
输出一个整数，表示最多能选取的藏身点个数。
【输入样例】
7 5 1 2 3 2 2 4 4 5 4 6【输出样例】
3【核心思想】
问题分析：给定一个包含N NN个节点M MM条边的有向无环图（DAG），需要选出最多的节点作为藏身点，使得任意两个藏身点之间都没有路径相连（即互相不可见）。这等价于求最小路径覆盖问题：用最少的不相交路径覆盖所有节点，每条路径上只能选一个节点作为藏身点。
算法选择：
- Floyd-Warshall 传递闭包：预处理图中任意两点间的可达性，将原图转化为传递闭包矩阵
- 二分图最大匹配（匈牙利算法）：将 DAG 的最小路径覆盖问题转化为二分图最大匹配问题
- Dilworth 定理：最小路径覆盖数 = 总节点数 - 最大匹配数
关键步骤：
- 建图：读入N NN个节点和M MM条有向边，构建邻接矩阵d [ i ] [ j ] d[i][j]d[i][j]表示i ii能否直接到达j jj
- Floyd-Warshall 求传递闭包：
- 三重循环遍历k , i , j k, i, jk,i,j
- 更新d [ i ] [ j ] = d [ i ] [ j ] ∨ ( d [ i ] [ k ] ∧ d [ k ] [ j ] ) d[i][j] = d[i][j] \lor (d[i][k] \land d[k][j])d[i][j]=d[i][j]∨(d[i][k]∧d[k][j])
- 最终d [ i ] [ j ] d[i][j]d[i][j]表示i ii是否可以通过任意路径到达j jj
- 构建二分图：
- 将每个节点拆分为左部和右部两个副本
- 若d [ i ] [ j ] d[i][j]d[i][j]为真（i ii可达j jj），则在左部i ii和右部j jj之间连边
- 匈牙利算法求最大匹配：
- 遍历每个左部节点i ii，尝试寻找增广路
- 使用s t [ ] st[]st[]数组标记右部节点是否在本轮被访问过
- 若找到匹配则匹配数r e s resres加1 11
- 计算答案：最小路径覆盖数 =N − r e s N - resN−res，即最多可选的藏身点数量
时间/空间复杂度：
- 时间复杂度：O ( N 3 + N ⋅ M m a t c h ) O(N^3 + N \cdot M_{match})O(N3+N⋅Mmatch)，Floyd-Warshall 为O ( N 3 ) O(N^3)O(N3)，匈牙利算法为O ( N ⋅ E ) O(N \cdot E)O(N⋅E)，其中E EE为二分图边数
- 空间复杂度：O ( N 2 ) O(N^2)O(N2)，传递闭包矩阵存储
最小路径覆盖与二分图匹配的核心思想：
- 最小路径覆盖：用最少的不相交路径覆盖 DAG 中所有节点，路径之间不能有公共节点
- Dilworth 定理：在 DAG 中，最小路径覆盖数等于总节点数减去对应二分图的最大匹配数
- 二分图构建技巧：将每个节点拆分为左右两份，原图的可达关系转化为二分图的边
- 匈牙利算法：通过寻找增广路不断扩大匹配，每次增广使匹配数加1 11
- 传递闭包：Floyd-Warshall 算法预处理可达性，将间接可达转化为直接边
- 适用于 DAG 上的路径覆盖、偏序集链划分、任务调度类问题
【算法标签】
#二分图
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;// ================= 常量与全局变量 =================constintN=205;// 最大节点数constintM=30005;// 最大边数（未使用，保留原样）intn;// 节点数量（左右部节点数相同）intm;// 边的数量boold[N][N];// 传递闭包矩阵：d[i][j] 表示 i 能否到达 j（有向边或间接可达）boolst[N];// 标记数组：记录右部顶点在当前轮匈牙利算法中是否被访问过intmatch[N];// 匹配数组：match[j] 记录右部节点 j 当前匹配的左部节点编号// ================= 匈牙利算法：尝试为左部节点 x 寻找增广路 =================// 返回值：是否成功为节点 x 找到匹配boolfind(intx){// 遍历节点 x 的所有可能右部匹配对象for(inti=1;i<=n;i++){// 如果 x 可以到达 i，且 i 在本轮搜索中还未被考虑if(d[x][i]&&!st[i]){st[i]=true;// 标记节点 i 已被本轮考虑// 情况1：节点 i 还未被匹配// 情况2：节点 i 已被匹配，但可以尝试为它的原匹配对象 match[i] 寻找新的匹配if(match[i]==0||find(match[i])){match[i]=x;// 将节点 i 匹配给节点 xreturntrue;// 成功找到匹配}}}// 尝试了所有邻接点都失败，返回 falsereturnfalse;}// ================= 主函数 =================intmain(){// 读取节点数和边数cin>>n>>m;// 读入 m 条有向边while(m--){inta,b;cin>>a>>b;d[a][b]=true;// 标记 a 可以直接到达 b}// Floyd-Warshall 算法求传递闭包// d[i][j] 最终表示 i 是否能通过任意路径到达 jfor(intk=1;k<=n;k++)for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)d[i][j]|=d[i][k]&d[k][j];// ========= 匈牙利算法求最大匹配 =========intres=0;// 记录最大匹配数// 为每个左部节点尝试寻找匹配for(inti=1;i<=n;i++){memset(st,false,sizeof(st));// 每轮搜索前重置标记数组if(find(i))// 如果成功找到匹配res++;// 匹配数加 1}// 输出结果：最小路径覆盖数 = 总节点数 - 最大匹配数cout<<n-res<<endl;return0;}【运行结果】
7 5 1 2 3 2 2 4 4 5 4 6 3
