一个图是二分图就一定能分成两部分而且每部分的点绝不会和自己这一部分的点直接相连。二分图的判断非常水直接黑白染色就行了。只要没有奇环就可以了。然后就会有很多板子题了。接着就是二分图的最大匹配问题。解决二分图的最大匹配通常用匈牙利算法。匈牙利算法常用于解决二分图的最大匹配以及最大权匹配问题。其实就是找到很多未匹配的边然后让未匹配的边与已匹配的边交替相连再把整条路径翻转让匹配数增加这就是基本思路。我们从左边每个点出发尝试找增广路每次只更新一条路径把所有左边点都跑一遍就能得到最大匹配了。代码cppbool dfs(int p){ if(vis[p])return false; vis[p]1; for(int i:e[p]){ if(!a[i]||dfs(a[i])){ a[i]p; return true; } } return false; } void solve(){ for(int i1;in;i){ memset(vis,0,sizeof(vis)); if(dfs(i))ans; } }补充几个相关的性质Kőnig 定理二分图中最小点覆盖的顶点数量等于最大匹配的边数量。证明显然然后是二分图上的最大独立集。这个可以根据Kőnig 定理推出来最大独立集 所有点数 - 最小点覆盖数。证明似乎也是显然的于是就可以用最大匹配的边数去求这些东西了。还有有向无环图上的最小路径覆盖其实路径数也是顶点数减去最大匹配。通过将每个点拆成出点和入点建出二分图求出最大匹配后就能把匹配边合并成若干条长路径剩下未匹配的点各自独立这样就能搞出来了。然后是最大权匹配问题。我们需要给每个节点 i 分配一个顶标 ()l(i)对于所有边 (,)(u,v) 满足 (,)≤()()w(u,v)≤l(u)l(v)。在一组可行顶标下原图的生成子图包含所有点中只保留满足 (,)()()w(u,v)l(u)l(v) 的边称为相等子图。显然可得定理对于某组可行顶标如果其相等子图存在完美匹配那么该匹配就是原二分图的最大权完美匹配。那么我们就可以从调整可行顶标的角度入手。要使得所有点都匹配上就从每个点开始枚举直到找到匹配为止。先把每个左边点的顶标初始化为它连出的最大边权然后依次枚举每个点。如果当前点无法找到增广路就找出与连接最接近的差值 d然后让所有访问过的左边点顶标减去 d右边点顶标加上 d这样既维持了平衡又能引入新的相等边继续匹配。因为每次调整至少会增加一条新边所以时间复杂度也是 (3)O(n3)。这样直接就搞出来了哈哈哈我简直是个天才。代码cppbool dfs(int p){ if(visx[p])return false; visx[p]1; for(int i1;ik;i){ if(!visy[i]lx[p]ly[i]e[p][i]){ visy[i]1; if(!a[i]||dfs(a[i])){ a[i]p; return true; } } else if(!visy[i])dmin(d,lx[p]ly[i]-e[p][i]); } return false; } int km(){ memset(ly,0,sizeof(ly)); for(int i1;ik;i){ lx[i]e[i][1]; for(int j2;jk;j)lx[i]max(lx[i],e[i][j]); } memset(a,0,sizeof(a)); for(int i1;ik;i){ while(1){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); d2e9; if(dfs(i))break; for(int j1;jk;j){ if(visx[j])lx[j]-d; if(visy[j])ly[j]d; } } } int ans0; for(int i1;ik;i)anse[a[i]][i]; return ans; }当然这是求最大值的做法最小值有个比较简单的方法直接把边权搞成负数属于是简单无脑了。这样二分图的内容就差不多了哈哈直接整完了。