本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing379. 捉迷藏 - 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 jjFloyd-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(N3N⋅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 上的路径覆盖、偏序集链划分、任务调度类问题【算法标签】#二分图【代码详解】#includebits/stdc.husingnamespacestd;// 常量与全局变量 constintN205;// 最大节点数constintM30005;// 最大边数未使用保留原样intn;// 节点数量左右部节点数相同intm;// 边的数量boold[N][N];// 传递闭包矩阵d[i][j] 表示 i 能否到达 j有向边或间接可达boolst[N];// 标记数组记录右部顶点在当前轮匈牙利算法中是否被访问过intmatch[N];// 匹配数组match[j] 记录右部节点 j 当前匹配的左部节点编号// 匈牙利算法尝试为左部节点 x 寻找增广路 // 返回值是否成功为节点 x 找到匹配boolfind(intx){// 遍历节点 x 的所有可能右部匹配对象for(inti1;in;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(){// 读取节点数和边数cinnm;// 读入 m 条有向边while(m--){inta,b;cinab;d[a][b]true;// 标记 a 可以直接到达 b}// Floyd-Warshall 算法求传递闭包// d[i][j] 最终表示 i 是否能通过任意路径到达 jfor(intk1;kn;k)for(inti1;in;i)for(intj1;jn;j)d[i][j]|d[i][k]d[k][j];// 匈牙利算法求最大匹配 intres0;// 记录最大匹配数// 为每个左部节点尝试寻找匹配for(inti1;in;i){memset(st,false,sizeof(st));// 每轮搜索前重置标记数组if(find(i))// 如果成功找到匹配res;// 匹配数加 1}// 输出结果最小路径覆盖数 总节点数 - 最大匹配数coutn-resendl;return0;}【运行结果】7 5 1 2 3 2 2 4 4 5 4 6 3