匈牙利与KM算法

[在我的博客园查看](https://www.cnblogs.com/suxxsfe/p/12989271.html) 二分图（可以带权）中的最大匹配问题，一般图要用带花树 ~~（并不会~~ # 一些定义 一些定义和性质可能在算法讲解中用不到，但是下面的题目中会用到 - 二分图：能将原图点集 $V$ 分成两个集合 $A,B$，且 $A\cap B=\emptyset,A\cup B=V$，使得所有边的端点一个在 $A$ 中，一个在 $B$ 中的图 - 匹配：一个边的集合，集合内的任意两个边都没有公共端点，那么集合内的边是匹配边，不在集合内但在原图边集内的边是非匹配边，匹配边的端点是匹配点，其它点是非匹配点 - 最大匹配：一个图所有的匹配中，包含匹配边最多的匹配的匹配边数 - 交替路：从非匹配点开始，走非匹配边，匹配边，非匹配边.....的路径 - 增广路：以非匹配点结束的交替路，显然，这种路径可以通过匹配边非匹配边的互换来产生更多的匹配。也可以理解为是把增广路里的匹配边集合与这条路径上所有边的集合做对称差，对称差是啥下面有 - 完美匹配：所有点都是匹配点的匹配 - 独立集：点的集合，集合内任意两个点没有边相连 - 团：点的集合，集合内任意两个点都有边，也就是一个完全子图 # 性质 ## 二分图等价于无奇环 匈牙利算法也要基于这点 首先有奇环一定不是二分图，奇环上的点满足不了二分图性质 再说明充分性，下面讨论的是每个联通块的情况，也就是为了应对图不连通 任意取一个顶点 $x$，把点分成两个集合，$A$ 中点到 $x$ 距离为奇数，$B$ 中点到 $x$ 距离偶数，尝试说明所有边都是一个端点在 $A$，一个端点在 $B$ 对于任意一条边 $(u,v)$，考虑从 $x$ 到 $u,v$ 的最短路，它们会有重合的顶点，即使可能只有一个 $x$ 是重合的 - 如果最后一个重合的顶点是 $u$ 或 $v$，那么 $x$ 到它们的最短路（距离）差 $1$，奇偶性不同，不在同一集合 - 不是 $u$ 或 $v$，设最后一个公共的是 $p$，设它们在同一集合，那么 $dis(p,u),dis(p,v)$ 奇偶性相同，那么 $p\rightarrow u\rightarrow v\rightarrow p$ 是个奇环，矛盾 ## 二分图中，最大独立集点数加最大匹配数等于总点数 这个结论在图论里也是比较常见的，下面一个题也用到了 设点数为 $V$，最大匹配数是 $M$，最大独立集点数是 $U$ 首先，由于 $M$ 对匹配的点都是相连的，所以必定有 $M$ 个点不在最大独立集中，那么 $U\le V-M$ 其次显然有 $U\ge V-2M$，就是不在最大匹配里的点都可以进入最大独立集。同时注意到，对于最大匹配中的一个匹配边的两点，总能找出一种方案让每对顶点都选出一个进入最大独立集（构造出来的不行的一定会与最大匹配矛盾） 这样又多出 $M$ 个，$U\ge V-M$ 综合上述得出 $U+M=V$ ## 无向图最大独立集等于它补图的最大团 这个显然吧，任意两个点没有变放在补图里就是任意两个点都有边 ## 增广路定理 这个也是匈牙利算法的基础，说的是**匹配数最大等价于不存在增广路** 不存在增广路的必要性很好证明，如果有增广路，因为增广路结构是非匹配边，匹配边......非匹配边，那么把所有匹配边和非匹配边交换就行了 这样匹配数加一，则原来的匹配不是最大匹配 充分性稍难，[证明思路是看的维基](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm#Augmenting_paths) 要先定义两个集合的“对称差”，如果某元素在且只在其中的一个集合中（不能同时在两个中），那么这个元素在这两个集合的对称差集合中，类似于异或 我们设当前的匹配是 $M$，最大匹配是 $M'$，那么做它们的对称差：$P=M\oplus M'$ 这个 $P$ 中，包含了所有在 $M$ 中，不在 $M'$ 中，和在 $M'$ 不在 $M$ 中的边 又因为 $M,M'$ 都是匹配，则每个 $P$ 中边的所有端点度数至多为二，所以更进一步说，$P$ 包含： 1. 一些**不相交的**环 2. 一些路径 这两种情况中，在 $M$ 中的边和不在 $M$ 中的边（在 $M'$ 中）个数相同 原因是，对于路径，肯定是一个边在 $M$，一个不在，交替下去，长度为偶数 如果不是，那么如果一个路径开头结尾都是一个集合内的点，那么必然会**对另一个集合产生增广路** $M'$ 里没有增广路 而对于 $M$ 里的增广路，这里为了说明方便先忽略这种情况，会在后面说明 对于环，肯定交替，没有上面说的产生增广路的事 又因为 $M'$ 是最大匹配，$M$ 不是，所以 $P$ 中的边肯定是来自 $M'$ 中的多 但对于第一种情况，边数相同，所以，这些多出来的边，肯定是第二种情况中，开头结尾都是 $M'$ 中的边，也就为 $M$ 产生了增广路（就是刚才说先不考虑的那种情况） 这就说明了，对于一个不是最大匹配的匹配，一定存在增广路 由此，可以得知，没有了增广路，一定是最大匹配 # 匈牙利算法 ~~终于开始正题了~~ 匈牙利算法实际上就是一个不断找增广路直到找不到的过程，用于无权二分图最大匹配 [洛谷P3386 【模板】二分图最大匹配](https://www.luogu.com.cn/problem/P3386)，[UOJ#78. 二分图最大匹配](http://uoj.ac/problem/78) 枚举二分图中每个左边（右边当然也可以，此处以左边为例）的点，从他开始找增广路，并记录下路径，做更改 如何寻找？dfs和bfs其实都可以 先说dfs，这里就不用单独记录路径了，直接记录在dfs的栈里 对每一个左边的点 $u$，枚举出边 $(u,v)$ - 如果 $v$ 当前没有匹配，那么 $v$ 就是增广路的最后一个点，回溯，对于路径上（也就是栈中）的每一对 $(u,v)$，它们互为对应的匹配点 - 如果 $v$ 匹配了，把它对应的匹配点作为新的 $u$，进入下一层递归，也就是说，如果再从这个新的 $u$ 递归的时候发现了增广路，要拆开 $v$ 和他的原匹配（下一层递归中新的 $u$），并把它和本次的 $u$ 匹配上 举个简单的例子，虽然是个很特殊的情况但也足够说明这个寻找的过程 依然是红色代表匹配边  1. $u=1,v=2$，发现 $v$ 有匹配，于是从 $v$ 的匹配也就是 $3$ 开始继续递归 2. $u=3,v=4$，然后再递归到 $u=5,v=6$，和上述过程相同 3. $u=5,v=6$，发现 $6$ 当前没有匹配，是一个增广路的终点，于是 `match[u]=v,match[v]=u`，回溯 4. 回溯到了 $u=3,v=4$ 的情况，拆开 $4$ 的原匹配，使得它和 $3$ 互相匹配 5. 回溯到 $u=1,v=2$ 也是相同 如果搜索了一圈，发现怎么也找不到增广路，那么此时答案就不能增加，否则答案加一 我看模板题的题解里把这个描述成“协商与匹配”，其实就是通过增广路的原理重新调整匹配与非匹配边，当然本质上一样 放上代码 ```cpp int n,m,e; int match[N],check[N];//match 记录对应的匹配点，check 记录有没有被访问 inline int dfs(int u){ for(reg int v,i=G.fir[u];i;i=G.nex[i]){ v=G.to[i]; if(check[v]) continue; check[v]=1; if(!match[v]||dfs(match[v])) return match[v]=u,match[u]=v,1;//维护新的匹配信息 } return 0; } int main(){ n=read();m=read();e=read(); for(reg int a,b,i=1;i<=e;i++){ a=read();b=read(); G.add(a,b+n); } int cnt=0; for(reg int i=1;i<=n;i++){ std::memset(check,0,sizeof check);cnt+=dfs(i); } std::printf("%d",cnt); return 0; } ``` 还有一种bfs版本，原理相同，但在稀疏图中跑的似乎比dfs快得多（网上看的，具体实验没自己做） 但码量更大，而且有的题目只能使用dfs或bfs其中一种，下面例题里有例子 bfs需要开一个 `pre` 数组来记录路径 和上面一样，对每一个左边的点 $u$，枚举出边 $(u,v)$，如果 $v$ 没匹配，借助 `pre` 数组，沿着走过的路径一路走回去，标记匹配，怎么借助在下面 如果匹配了，就把原匹配点加入队列，并记录 `pre[match[v]]=u`，这里 `match` 数组记录的就是原匹配 什么意思呢？具体来说 `pre[i]` 是路径上点 $i$ **往回的第二个节点** 是在上一个**新的（增广路修正后的）**匹配边中，**同样位置**的点，看下图，红边是当前记录的匹配边  注意图中说的 `e=match[d]` 指的是更新信息前的 `match[d]` 那么经过对增广路的匹配非匹配边的调换，得到下面的样子：  那么我们成功从 $u$ 找到增广路，答案加一 代码 ```cpp int num_left,num_right,m; int pre[N],match[N]; //match[i]，表示一条包含点 i 的匹配边的另一个端点 //pre[i]，维护几个匹配边和未匹配边组成的路径信息，具体来说 pre[i] 是路径上往回的第二个节点 //比如增广路1->2->3->4->5，其中，1->2，3->4 是匹配边，那么 pre[4]=2 //也就是，我们可以通过 d=pre[d]，来让 d 变成上一个匹配路径中，和 d 在同一个位置中的点 //这就是更新路径信息时的做法 int que[N],tail,head,check[N]; inline int max_match(){ int ans=0,u,v; for(reg int i=1;i<=num_left;i++){ tail=head=0;que[0]=i; pre[i]=0; while(tail<=head){ u=que[tail++]; for(reg int j=G.fir[u];j;j=G.nex[j]){ v=G.to[j]; if(check[v]==i) continue;//本次 bfs 访问过 check[v]=i; if(match[v]) pre[match[v]]=u,que[++head]=match[v]; //是匹配点，那么把已经和他匹配的另一个点入队 else{//找到未匹配点，是个增广路，要更新路径 int d=u,e=v,t; while(d){ //d 是增广路上匹配边的终点，e 是增广路上下一个匹配边的起点 //然后让 d,e 互相匹配 //然后通过 e=match[d],d=pre[d] 来推到前一条边，此时 d,e 仍满足前一行说的性质 t=match[d]; match[d]=e;match[e]=d; d=pre[d];e=t; } goto BREAK; } } } BREAK:; if(match[i]) ans++; } return ans; } int main(){ num_left=read();num_right=read();m=read(); for(reg int u,v,i=1;i<=m;i++){ u=read();v=read()+num_left;G.add(u,v); } std::printf("%d",max_match()); return 0; } ``` 容易发现，复杂度 $O(nm)$，但其实跑不满 # 二分图最大权匹配 这个是叫KM算法，用在带权值的二分图上，找一些匹配边使得它们权值之和最大 求最大匹配时，要求所有边权非负；当有负数边权是，可以求出一个最大的完美匹配 [UOJ#80. 二分图最大权匹配](http://uoj.ac/problem/80) 首先，这个算法是针对于完全图，不过也没有什么本质区别，就把不在实际中的边边权设为零就好。 并且二分图左右两边的点数相同，这个就取一个 $\max$ 然后本来不存在虚拟的加进去的点就全都连零边就好 很显然，根据上面所说的，完全图的最大权匹配一定是完美匹配（边权非负） 为每个顶点确定一个“顶标”，$lx_u,ly_u$ 分别表示二分图左右两边节点的顶标 定义“可行顶标”，是使得对于边 $(u,v)$，有 $$lx_u+ly_v\ge W_{u,v}$$ 的顶标 在定义“相等子图”，是对于一个子图内（包含原图**所有顶点**，但不一定包含所有边），任意边 $(u,v)$ 有 $$lx_u+ly_v=W_{u,v}$$ 的子图 由这个相等子图性质，我们有以下结论，对于一个包含完美匹配的相等子图，则这个子图的最大权匹配的权值和，就是所有顶标加起来 同时，也是这个子图的最大权匹配 进一步讲，也是原图的最大权匹配和，因为如果去除掉子图完美匹配的某些边，加入另一些边，使得它还是一个完美匹配 那么这些加入的边的权值肯定是小于等于两端点顶标和，所以总体地看，他就小于等于所有顶标和，也就不是最大权匹配了 所以总结出来就是：**相等子图存在完美匹配，则该匹配是最大权匹配** 那么，我们不断调整顶标，使得相等子图存在完美匹配不就行了 于是算法的大体结构出来了 1. 以一个点为起点跑bfs或dfs，看能不能增广 这个bfs或dfs和匈牙利算法中每一次进行的搜索类似，就是注意走的边要是满足 $lx_u+ly_v=W_{u,v}$ 的边 以下说的“搜索”，就是指这个过程 2. 能增广就再去下一个点，不能就调整顶标 3. 再跑bfs或dfs，再调整顶标，直到能增广 然后实际中，第三步跑好多遍搜索是可以优化掉的，而且事实上不把他优化掉的话交到UOJ会T掉 不过还是先来看如何调整顶标，这是算法的关键 要先初始化顶标，一个可行的初始化是对于每个 $lx_i$，让它取所以和 $i$ 相连的边的权值最大值，同时 $ly_i=0$ 用 $vis_i$ 表示每个顶点是否在搜索中访问过，我习惯把左右边的编号放在一起，所以就不区分成多个数组了 维护一个 $d_j=\min(lx_i+ly_j-W_{i,j}\mid vis_i=1,vis_j=0)$，和一个 $now=\min(d_j\mid vis_j=0)$ 这个什么意思？ 就是我们要找到一个最小的 $now$，使得让所有可以被搜索到的左边的节点，减去 $now$ 这样，他就**一定**能访问到一个右边的**还没有被访问**的节点，也就能访问到这个节点的对应匹配（如果有的话） 注意这里是一定，这有关算法复杂度 那为什么要最小呢？我们要让其它边**两端节点可行顶标的性质不被破坏** 而要让以前在相等子图中的点，还在相等子图，所以要让所有能搜索到的右节点，顶标加上 $now$ 其实严格来讲这里还不能称作相等子图，因为还没有包含所有点 然后顶标的变化需要调整 $d_j$，实际上就是 $d_j=d_j-now$，原因很简单，在注释里 那么，哪一个 $d_j$ 被减成了零，左边能搜索到的点能**新访问到的右边节点**就是哪个（或者哪几个） 设这个节点为 $to$，姑且不考虑有好几个的情况，那会在多遍循环中被处理完 - 则如果 $match(to)$ 还没有定义，则说明我们找到了增广路，退出循环找下一个点即可 - 如果定义了，那么可以把 $to,match(to)$ 都纳入可以搜索到的点，也就是把它们的 $vis$ 变成 $1$，然后再对于 $vis_j=0$ 的 $j$ 更新 $d_j$ 即可 再次更新，是因为 $match(to)$ 被打上了 $vis$ 标记 属于了左边能到达的点，所以要对于每个 $vis_j=0$ 的 $j$ 和 $match(to)$ 来更新 $d_j$ 直到循环被跳出 然后跳出以后，要再跑一遍搜索，来更新一下 $match$ 复杂度：最外层循环循环 $n$ 遍，里层需要被跳出的循环中，更新顶标和 $d_j$ 啥的都是 $O(n)$，而每次都会有两个点 $vis$ 变成 $1$，所以最多循环 $O(n)$ 遍 那么总复杂度 $O(n^3)$，~~感觉也不会跑满~~，主要是因为 $n$ 代表的其实是左边或右边点的个数，所以实际上要乘个 $\frac{1}{8}$ 的常数，那么 UOJ $n=800$ 就能过了 然后发现那个第三部的搜索自然而然的优化掉了 其实不优化掉的方法是不维护 $d_j$，每次求这个值的方法就是跑一遍搜索，而这里是用了动态的更新它来减少搜索次数 这部分可能比较难理解，可以看代码中的注释 ```cpp #define N 808 int num_left,num_right,m; int G[N][N]; int vis[N],pre[N],match[N],lw[N],d[N]; int que[N],tail,head; inline int bfs(int u){ tail=head=0;que[0]=u; pre[u]=0; while(tail<=head){ u=que[tail++];vis[u]=1; for(reg int i=num_left+1;i<=num_right;i++)if(G[u][i]==lw[u]+lw[i]){ if(vis[i]) continue; vis[i]=1; if(match[i]) pre[match[i]]=u,que[++head]=match[i]; else{ int d=u,e=i,t; while(d){ t=match[d]; match[d]=e;match[e]=d; d=pre[d];e=t; } return 1; } } } return 0; } inline LL max_match(){ for(reg int i=1;i<=num_left;i++){//初始化 lx for(reg int j=num_left+1;j<=num_right;j++) lw[i]=std::max(lw[i],G[i][j]); } for(reg int i=1;i<=num_left;i++){ std::memset(vis,0,sizeof vis);std::memset(d,0x7f,sizeof d); if(bfs(i)) continue;//能增广了就退出找下一个 for(reg int j=1;j<=num_left;j++)if(vis[j]) for(reg int k=num_left+1;k<=num_right;k++) if(!vis[k]) d[k]=std::min(d[k],lw[j]+lw[k]-G[j][k]); while(1){ int now=1e9,to,s; for(reg int j=num_left+1;j<=num_right;j++)if(!vis[j]) now=std::min(now,d[j]); for(reg int j=1;j<=num_left;j++)if(vis[j]) lw[j]-=now; for(reg int j=num_left+1;j<=num_right;j++) if(vis[j]) lw[j]+=now;//为了维持以前在相等子图的点还在相等子图，左边点减 now，右边加 now else d[j]-=now,to=d[j]?to:j;//to 记录了哪个是要被连接到（d[j]=0，加入相等子图）的右顶点 //d[j]-=now 是因为对于 vis[j]=0 的 j，它们所连到的左边的满足 vis[k]=1 的点的 lx[j] 会减 now //那再取个 min 还是减 now //这样更新了 d[j] 还求出了 to if(!match[to]) break; s=match[to];vis[to]=vis[s]=1;//打上 vis 标记 for(reg int j=num_left+1;j<=num_right;j++) //更新 d，这里再次更新，是因为 match[to] 被打上了 vis 标记 //属于了左边能到达的点，所以要对于每个 j 和 match[to] 来更新 d[j] if(!vis[j]) d[j]=std::min(d[j],lw[s]+lw[j]-G[s][j]); } std::memset(vis,0,sizeof vis); bfs(i); } LL ans=0; for(reg int i=1;i<=num_right;i++) ans+=lw[i]; //答案直接把每个 lx,ly 加起来就行了，因为最后是个完美匹配 return ans; } int main(){ num_left=read();num_right=read();m=read(); int nnn=num_left; num_left=num_right=std::max(num_left,num_right); num_right+=num_left; for(reg int u,v,i=1;i<=m;i++){ u=read();v=read()+num_left;G[u][v]=G[v][u]=read(); } std::printf("%lld\n",max_match()); for(reg int i=1;i<=nnn;i++) std::printf("%d ",(match[i]&&G[i][match[i]])?(match[i]-num_left):0);//边权要大于一，是实际中的边 return 0; } ``` # 题目 题目还是匈牙利的居多，二分图权匹配的题本来好像就不多 ## P2055 [ZJOI2009]假期的宿舍 [here](https://www.luogu.com.cn/problem/P2055)，同[bzoj1433](https://darkbzoj.tk/problem/1433) 一些学生，一部分在校（有宿舍的床），一部分是外校的（没床） 在校的学生有一些要回家（不占用床），外校的学生都要来来学校（占用床），当然，不回家的在校学生也占床 给出一些朋友关系（双向），每个人只能睡自己或朋友的床，问能不能安排合适的方案使得每个人都有床 比较简单，为每个在校学生新建一个点，表示它们的床的编号，这样看谁能睡谁的床，向他的床连边就行 人和人，床和床不会连边，所以是二分图，跑一下匈牙利看一看匹配数是不是和需要床的人数相等即可 注意不回家在校生可以睡自己的床 [code](https://www.luogu.com.cn/paste/b1dwi0pp) ## P6268 [SHOI2002]舞会 [here](https://www.luogu.com.cn/problem/P6268) 求无向图最大独立集，用刚才证明的性质，二分图的最大独立集大小是顶点个数减去最大匹配数 是二分图是因为曾经跳过舞的一定是男生与女生 太裸，代码就不放了 ## P1129 [ZJOI2007]矩阵游戏 [here](https://www.luogu.com.cn/problem/P1129)，同[bzoj1059](https://darkbzoj.tk/problem/1059) $n\times n$ 的黑白格子，每次可以交换两行或两列 问能不能通过若干次交换使得左上到右下的对角线全为黑 对于第 $i$ 行来讲，如果他在第 $a_{i,j}$ 是黑色，那么，显然说明它可以被交换到第 $a_{i,j}$ 行上去，来保证对角线是黑 然而列交换就没有任何意义，如果两列本来就都有黑色，那么这两列就都可以被满足此列的对角线上的格子是黑 而如果其中一个没有黑色，那么交换一下被交换的那个列又没有黑了，还是不行 当然把上面描述中的“行”和“列”都互换也是一样的 所以，只要对于每个黑格 $a_{i,j}$，就把 $i,j$ 连边即可 就是分别建立节点表示行号和列号，是个二分图，直接匈牙利 [code](https://www.luogu.com.cn/paste/2jx5zld5) ## P1963 [NOI2009]变换序列 [here](https://www.luogu.com.cn/problem/P1963)，同[bzoj1562](https://darkbzoj.tk/problem/1562) 一个 $1$ 到 $n$ 的序列，求一个排列 $T$，要求每个数在 $T$ 中指定的两个位置中的一个 问有没有解，如果有，输出字典序最小的 $T$ 首先有没有解很好判，建个点数 $2n$ 的图，分别代表原序列中的每个数，和 $T$ 中的每个数 这是个二分图，且左右点数相同，然后看一下有没有完美匹配就行了 这个 $T$ 的一种可行解就是所有点的 `match` 关键是如何让字典序最小 回顾之前说的匈牙利算法的过程，先成为匹配边的边，在后面的节点寻找增广路时，如果它们能组成增广路，则会在修正这个增广路以产生更多匹配数而被“抹掉”，也就是成为非匹配边 字典序是先比较前面字符的大小，那么肯定是最小化前面的点的 `match` 那么，我们在从每个点为起点找增广路时，从 $n$ 到 $1$ 循环，就行了 然后为了让每个点在不被其它点影响的情况下，得到最小的对应匹配点，就也要让编号小的点先被访问 邻接表的访问是倒序的，所以就先加入序号大的边就行了 这里就是刚才提到的不能用bfs的情况 因为为了字典序最小，找到一个可能成立的较小编号的点后，就要从这开始一直访问下去，如果不行在考虑其它点 而bfs时，从 $u$ 开始，访问到一个可能成立的较小点 $v$ 后，被加入队列 但如果又在访问其它 $v$ 时，直接成立了（也就是直接有了增广路），那么就退出循环了，但这样就错了 因此一定要根据实际情况看用bfs还是dfs 但似乎目前还并没有遇到dfs不行的题 [code](https://www.luogu.com.cn/paste/q264j2im) ## P1971 [NOI2011]兔兔与蛋蛋游戏 [here](https://www.luogu.com.cn/problem/P1971)，同[bzoj2437](https://darkbzoj.tk/problem/2437) 题面挺复杂，不简述了 这题做的我简直想打死兔兔和蛋蛋，一晚上+一上午+一中午差点死在这题上/kk 首先可以看作是这个空格子在移动，而且不会经过重复的点，所以只要经过了一个点不用，也不能再考虑这个格子了 如何说明不重复？假设空格子从 $u$ 离开，那么就是把离开的这个方向的格子移入到了原来空格的位置 那么要是想让空格子再回到 $u$，必然需要先走偶数不，来到 $u$ 周围四个格子之一，然后再用一步回去（因为每次移动的颜色不同的限制） 也就是一共走了奇数步，回到原来位置 把移动按横纵方向拆开，横纵方向都是走到一个格，再走回来，应该是偶数 基于这一点再做分析，考虑什么时候先手必胜 我们构造一个二分图，把黑点和空格的起始点放在左边，白点放在右边 对于另个相邻的格子，如果颜色不同，连边，表示能从这两个格子之间走过 这是个二分图，因为边在黑和白之间 如果对于**任意一种**最大匹配方式，先手操作前所在的格子都是匹配点，那么**先手必胜** 先手可以先走一个匹配边，那么后手走的就是非匹配边，以此类推，当一定会存在当先手走完一个匹配边后，后手无路可走的情况 因为一个格子在任意一种最大匹配中都是匹配点，那么以它开始的一个路径，肯定会是一种“**修正过的**增广路” 就是第一条，最后一条边都是匹配边 如果不是，那么以匹配边开始，非匹配边结束，就可以让所有边在匹配/非匹配中互换，则匹配数不变，起点却不是匹配点了 这种点，叫做最大匹配的**关键点** 如何判断？先跑出任意一种匹配方式，如果这个点都没匹配上肯定直接不是关键点 否则强制让这个点和他的原匹配不被匹配在一起，就是把匹配删掉 从他的原匹配开始搜索，看能不能再通过别的方式增广，能的话就说明不是，否则就是关键点 因为之前提到过，已经经过的点不能再次经过，所以还要用一个 `deleted` 数组记录是否被走过，之前一直卡在这 [code](https://www.luogu.com.cn/paste/7uw78x2f) ## CF1107F. Vasya and Endless Credits 这里开始是最大权匹配的题了 [here](https://codeforces.com/contest/1107/problem/F) 一共有 $n$ 中贷款，每个月月初可以办理到一种贷款，每种贷款只能办一次 每种可以贷到 $a$ 元，要在后来（包括刚开始贷款的这一个月）的月末还 $b$ 元，还 $k$ 个月为止 一开始没钱，问在某时刻，手中最多可以有多少钱 显然，整个贷款的过程不会超过 $n$ 个月 最终结束也是在一个月的月初，且这个月初刚开始一个贷款 如果第 $i$ 个贷款在整个过程的倒数第 $j$ 天开始，那么，一共要还 $b_i\min(k_i,j-1)$ 元 拿到了 $\max(a_i-b_i\min(k_i,j-1),0)$ 元，$0$ 表示如果收益是负数那就不办这个贷款 所以，可以建图，让 $1$ 到 $n$ 表示 $n$ 中贷款，$n+1$ 到 $2n$ 表示倒数第 $j$ 天 连边表示在倒数第 $j$ 天买了第 $i$ 种贷款 然后跑一个最大权匹配就行了 [code](https://codeforces.com/contest/1107/submission/81473490) ## P6061 [加油武汉]疫情调查 [here](https://www.luogu.com.cn/problem/P6061)，~~似乎是洛谷题库里唯一能搜到的二分图权匹配题~~ 一张**有向图**，用一些环和孤立的点覆盖所有点，环的代价是所有边的权值和，点的代价是点权，问最小代价 一开始没看见是有向的直接全WA/kk 先Floyd一下求出任意两点之间的最短路 然后发现，对于点 $i,j$，新建一个二分图，连边 $i,j+n$，并把权值设为 $i,j$ 最短路距离 然后每个 $i,i+n$ 连一个点权为权值的边 则一定存在完美匹配，而且每一个完美匹配都对应一个可行的覆盖方案 然后在模板代码上改一改改成求最小权匹配就行了 [code](https://www.luogu.com.cn/paste/as7l38jd)，发现用一个大数减去实际边权跑最大匹配再转换回来是不可行的 ## 其它题目 [P3033 [USACO11NOV]Cow Steeplechase G](https://www.luogu.com.cn/problem/P3033) [P4304 [TJOI2013]攻击装置](https://www.luogu.com.cn/problem/P4304) [P1640 [SCOI2010]连续攻击游戏](https://www.luogu.com.cn/problem/P1640) [P2825 [HEOI2016/TJOI2016]游戏](https://www.luogu.com.cn/problem/P2825) [匈牙利算法](https://www.luogu.com.cn/problem/list?tag=188&page=1) [最大匹配](https://www.luogu.com.cn/problem/list?tag=55&page=1) ------------------------- 作者太菜，一般图的最大匹配和最大权匹配并没有讲，~~发现光二分图的匹配算法和题就学了半天才弄懂~~ 难免会有错误，所以希望能在评论区或私信指出，感谢，~~轻喷~~