题目描述某学校要召开一个舞会。已知学校所有 n 名学生中有些学生曾经互相跳过舞。当然跳过舞的学生一定是一个男生和一个女生。在这个舞会上要求被邀请的学生中的任何一对男生和女生互相都不能跳过舞。求这个舞会最多能邀请多少个学生参加。输入格式输入的第一行是 n 和 m 。其中 n 是可选的学生的总数 m 是已知跳过舞的学生的对数 ( n≤1000 m≤2000 。然后有 m 行每行包括两个非负整数表示这两个编号的学生曾经跳过舞。学生的编号从 0 号到 n−1 号。输出格式输出文件仅一行为一个数字即能够邀请的最多的学生数。输入输出样例输入 #1复制运行8 6 0 2 2 3 3 5 1 4 1 6 3 1输出 #1复制运行5输入 #2复制运行20 5 5 2 4 3 18 17 0 11 13 3输出 #2复制运行161. 题意转换用一句话剥离题目的背景故事这道题本质上是在求在一个节点数为 N、边数为 M 且“阵营未明确标明”的二分图中求解其“最大独立集”的大小。2. 思考过程与解题思路面对这道题第一直觉的暴力解法是什么面对“最多能邀请多少人参加”的子集选择问题初学者的第一直觉往往是状压DP或DFS暴力回溯枚举这 n 个人到底“邀请”还是“不邀请”然后检查选出的人中是否存在跳过舞的组合。时间复杂度将高达 O(2^N)。考虑到本题数据范围 n≤10002^1000 的运算量必然会引发严重的超时。如何一步步推导到正解洞察隐含的图论性质题目有一句极其强烈的暗示——“跳过舞的学生一定是一个男生和一个女生”。这意味着如果我们把学生看作节点跳过舞的关系看作边那么所有的边都只存在于不同性别的群体之间绝对不存在同性之间的边。这完美契合了二分图的定义抽象问题模型“被邀请的学生中的任何一对男生和女生互相都不能跳过舞”即要求我们选出的节点集合中任意两个节点都没有边相连。在图论中这被称为求图的最大独立集。召唤二分图核心定理在二分图中有一个非常优美的结论最大独立集点数 图的总节点数 - 最小顶点覆盖数而根据柯尼希定理Königs theorem我们又知道最小顶点覆盖数 最大匹配数所以最多邀请人数 总人数 N - 最大匹配数。填补战术盲区染色法思路很完美但遇到了一个问题输入数据并没有告诉我们谁是男谁是女因此在跑匹配算法之前我们必须先使用DFS 染色法黑白染色把互相排斥的节点强行划分到“左部”和“右部”。3. 算法设计与样例推演核心算法与数据结构二分图染色DFS利用vis数组记录颜色0 未染1 左部2 右部。遇到未染色的相邻节点就染上相反的颜色。匈牙利算法利用基于 DFS 的增广路算法求出左部和右部之间的最大匹配数。邻接表vectorint vec1存储学生之间无向的跳舞关系。手玩推演核心逻辑以样例 1 为例总共 8 个点 (0~7)。给定的边为 (0,2), (2,3), (3,5), (1,4), (1,6), (3,1)。染色划分阶段 从 0 开始 DFSvis[0]1。 顺着边染色0(1) → 2(2) → 3(1) → 5(2) 以及 3(1) → 1(2) → 4(1) 和 1(2) → 6(1)。 最终左部集合vecl {0, 3, 4, 6,7}右部集合vecr {2, 5, 1}7是孤立点。匈牙利匹配阶段 遍历左集合寻找匹配 0 匹配 2 (成功) ;3 匹配 5 (成功) ;4 匹配 1 (成功);6 匹配 1 (失败1已被4占据且无法腾出位置);7 找匹配,因为没有连线直接失。最大匹配数为 3。计算答案 最多邀请人数 总人数 8 - 最大匹配数 3 5 人。与样例输出完全一致。4. 时空复杂度分析时间复杂度染色阶段遍历全图复杂度为 O(NM)。匈牙利算法阶段外层循环最多 N 次每次 DFS 最坏遍历 M 条边复杂度为 O(N×M)。总时间复杂度为 O(N×M)。本题 N≤1000,M≤2000最大运算量约 2×10^6在 C 1 秒的时限内飞速跑完。空间复杂度使用了多个大小为 2010 的一维数组和vector存图。空间复杂度为 O(NM)内存开销极小约几MB远低于题目要求的 125MB绝对不会 MLE。5. 坑点与易错总结节点编号从 0 开始这是一大杀手习惯了从 1 开始编号的同学如果在初始化linked数组时默认用 0会导致 0 号节点被误认为“尚未匹配”。必须严格使用memset(linked, -1, sizeof(linked))。图不连通多个独立社交圈人群中可能存在多个互不相交的关系网。如果在染色时只写一句dfs(0, -1)会导致其他圈子的人未被分组。必须使用for循环遍历判断vis[i] 0来开启多源染色。单向存边还是双向存边在还没染色前我们根本不知道谁是左部谁是右部因此读入数据时必须双向存边。6. 代码进阶与优化剖析核心教学点审视下方我提供的代码整体逻辑极其严密防坑意识绝佳尤其是对 0 编号和图不连通的处理。但要成为金牌选手我们需要关注以下常数优化高阶技巧匈牙利算法的“时间戳”常数优化断崖式提速看我的hungary()函数外层每遍历一个点v都要执行一次memset(used, 0, sizeof(used))。这意味着如果左部有 1000 人就要把数组全盘擦除 1000 遍引入了 O(N^2) 的基础常数开销。优化思维其实我们只需要把当前的轮次标记比如正在帮左边的u找对象把u1作为timestamp加1是为了避开0传进dfs2(int u, int timestamp)。把内部的判断条件!used[v]升级为used[v] ! timestamp然后used[v] timestamp。效果旧轮次的标记天然不会干扰新轮次外层的memset可直接删除这会让你的代码在面对严苛时限时拥有更强的生存能力。7. 完整代码//这道题也是要画图瞅瞅 //先左边画8个点0-7 右边画8个点0-7 然后不能一起来的就连线 //发现这样好像不太对因为左边和右边的点其实是有重复的但是只要这个点左边不选右边也不应该存在这个点的 //所以我们要想办法把不能一起出现的点分成左边一拨和右边一拨染色法 dfs遍历 //然后找出这个一批点最大匹配 然后总点数-最大匹配就是我们要求的能够邀请的最多的学生数了 #include iostream #include vector #include cstring//memset要用 using namespace std; int n,m; vectorint vec1[2010];//存起始的不能互相跳舞的男女队 int vis[2010];//vis[i]1代表i点被染色成1 vis[i]2 代表i点被染色成2 vis[i]0代表还没有被染色 vectorint vecl;//存左边的那拨点 vectorint vecr;//存右边的那拨点 int used[2010];//标记右边的那拨点在本轮循环中是否被使用过 int linked[2010];//右边的点所匹配的左边的点 //x是这轮dfs的起点 fa为父节点防止重复访问 void dfs(int x,int fa){ //遍历所有与x有边相连的点v for(int v:vec1[x]){ //避免重复访问 if(vfa) continue; //如果v点还没有被染色 if(vis[v]0){ //v与x不能是同一种颜色 if(vis[x]1) vis[v]2; else vis[v]1; //继续遍历 dfs(v,x); } } } //u为这一轮循环的左点 //【优化】进阶可扩充为bool dfs2(int u,int timestamp) 用时间戳取代每次的memset bool dfs2(int u){ //遍历所有与u有边相连的右点 for(int v:vec1[u]){ //如果v点这一轮循环还没有使用过 if(!used[v]){ //把v点标记为使用过 used[v]1; //若v还匹配左点 或者匹配v的那个左点能找到新的匹配的右点 if(linked[v]-1 || dfs2(linked[v])){ linked[v]u; return true; } } } return false; } //匈牙利算法求最大匹配 int hungary(){ int idx0;//记录最大匹配数 //初始化右边的所有点都没有匹配左边点值为-1 memset(linked,-1,sizeof(linked)); //接下来遍历所有左点 for(int v:vecl){ //每一轮循环前要初始化所有右点都没有使用过 // 【优化】若使用时间戳优化 这行memset即可省略 常数下降 memset(used,0,sizeof(used)); if(dfs2(v)) idx; } return idx; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //存图 for(int i1;im;i){ int a,b;//a和b为互相跳过舞的男女生 cinab; //无向边双向存边 vec1[a].push_back(b); vec1[b].push_back(a); } //染色 把不能一起去的学生分成两拨 从0号学生开始进行dfs //为了防止图有多个联通块 需要开for循环遍历每个没有被染色的点 for(int i0;in;i){ //如果i点还没有被染色 if(vis[i]0){ vis[i]1;//就把它染色为1 dfs(i,-1);//然后从i点开始dfs 起点没有父节点设为-1 } } //接下来所有点已经被分成了左右两拨 for(int i0;in;i){ //颜色为1的存进左边那拨点 if(vis[i]1) vecl.push_back(i); //颜色为2的存进右边那拨点 else vecr.push_back(i); } //接下来进行匈牙利算法 找最大匹配 //最大独立集总点数-最大匹配数 coutn-hungary(); return 0; }