爵士OIer查看:3 回复:16 评论:3 创建时间:2020-05-05T17:52:15用户:爵士OIer查看:3 回复:16 评论:3 创建时间:2020-05-05T17:52:15
【C++基础教程】蒟蒻也能懂算法：二分图从入门到提高
对于n皇后问题和覆盖问题，最基础的算法是无优化DFS（深度优先搜索）和状态压缩动态规划。这两种都是时间复杂度比较高的算法。还有什么其他方法呢？
二分图
如图，一个图的点集可以划分为两个不相交的子集，每一个子集中的点和该子集中的其他点没有边相连的图就叫二分图。比如上面有两个点集u,v符合上述条件，则它是一个二分图。
二分图的判定
· 定理：一个无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）
· 根据该定理，可用染色法判定二分图：尝试用黑、白两种颜色标记图中的节点，当一个节点被标记后，它的所有邻接点应被标记为与它相反的颜色。若发生冲突，说明图中存在奇环。二分图染色一般基于DFS实现，时间复杂度为O(N+M)。
· 判定流程伪代码如下：
void dfs(int x,int color){
v[x]=color; //对点x染色
//遍历x相连的无向边(x,y)
if (v[y]==0) //未染色
dfs(y,3-color); //黑1，白2，3相减取反色
else if (v[y]==color)
//该无向图不是二分图，算法结束
//是无向图，算法结束
}
//在主函数中
for (int i=1;i<=n;i++)
if (v[i]==0) dfs(i,1);
二分图匹配
· 【任意两条边都没有公共端点】的边的集合称为图的匹配。
· 最大匹配（maximal matching problem)就是包含边的个数最多的匹配。
上面是一种匹配方式，但是不一定是最大匹配。
二分图匹配的用途很多，如自来水管、车站打车等。
增广路
· 对于任意一组匹配M（M是一个边集），属于M的边被称为“匹配边”，不属于M的边被称为“非匹配边”。
· 匹配边的端点被称为M的“饱和点”，其它节点被称为“非饱和点”
· p是G的一条通路，如果p中的边为属于M中的匹配边与不属于M的非匹配边交替出现，则称p是一条M-交错路。
· p是一条M-交错路，如果p的起点和终点都是非M-饱和点，则称p为M-增广路。
如上两图，左图是一种匹配。右图是一种更大的匹配。
· 增广路显然具有以下性质
1.长度len是奇数
2.路径上第1，3，5，……，len条边是非匹配边，第2，4，6，……，len-1条边是匹配边。
· 如果将增广路p上所有边的状态取反，即原来的边变为非匹配边，原来的非匹配边变成匹配边。那么新得到的边集M’仍然是一组匹配，并且匹配边数增加了1。由此可得推论：
· 二分图的一组匹配M是最大匹配，当且仅当图中不存在M的增广路。
匈牙利算法（增广路算法）
· 匈牙利算法，又称增广路算法，用于计算二分图最大匹配。其主要过程为：
1.设M为空集，即所有边都是非匹配边。
2.寻找M的增广路p，把路径上的所有边的匹配状态取反，得到一个更大的匹配M’。
3.重复第2步，直至图中不存在M的增广路。
· 该算法的关键在于如何找到一条增广路：依次尝试给每一个左部节点x寻找一个匹配的右部节点y。右部点y能与左部点x匹配：需要满足以下两个条件之一：
1.y本身就是非匹配点
此时无向边(x,y)本身就是非匹配边，自己构成一条长度为1的增广路。
2.y已经与左部点x’匹配，但从x’出发能找到另一个右部点y’与之匹配。
递归进入该左部点，为其寻找匹配的右部点，此时路径x~y~x’~y’为一条增广路。
· 在实际的程序实现中，可采用DFS的框架，递归地从x出发寻找增广路。若找到，则在深搜回溯时，正好把路径上的匹配状态取反。另外可以用全局bool数组标记节点的访问情况，避免重复搜索。
下面贴出具体流程，方便理解。
图一到图五很好理解，不讲；
可以看到，在图六中出现了两条红色的边。搜索到第四个白色点时，出现了下面这条红色的边，占用第三个黑色点。因此，第二个白色点重新建边，搜索与第二个白色点相邻的黑色点，搜索到了第一个黑色点，出现上面这条红色的边，发现这个黑色点如果被占用，那么第一个白色点将会无法建边，回溯；
到图七，第二个白色点搜索与没有被占用且与其联通的第四个黑色点，建边（图七中新出现的红色边），形成增广路。
至此，DFS过程结束。形成图八那样的一种从第一个白色点出发的最大匹配。
· 匈牙利算法的正确性基于贪心策略，它的一个重要特点是：当一个节点称为匹配点后，至多因为找到增广路而更换匹配对象，但是绝不会再变回非匹配点。
· 对于每个左部节点，寻找增广路最多遍历整张二分图一次。因此，该算法的时间复杂度为O(NM）。
Code：
bool dfs(int x){
int i,y;
for(i=head[x]; i>0; i=next[i]) //考虑与x相连的每个点y=ver[i]
if(!visit[y=ver[i]]){//没有被搜索过
visit[y]=1;
if(!match[y] || dfs(match[y])){
match[y]=x; return true;
}
}
return false;
}
//下面是主函数核心部分
for(int i=1;i<=n;i++){
memset(visit,0,sizeof(visit)); //清空访问标记
if(dfs(i)) ans++; //从左部点i出发寻找增广路
}
二分图匹配的模型
· 二分图匹配的模型有两个要素
1.节点能分成两个独立的集合，每个集合内部有0条边。
2.每个节点只能与1条匹配边相连。
例题：匈牙利算法-棋盘上的问题
还记得开篇的n皇后和状压DP吗？
棋盘覆盖
问题描述
给定一个N行N列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
输入格式
第一行包含两个整数N和t，其中t为禁止放置的格子的数量。
接下来t行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
输出格式
输出一个整数，表示结果。
数据范围
1≤N≤100
输入样例
8 0
输出样例
32
解题思路：
相信大家一看到就以为是状压DP吧（雾
我们怎么用二分图的匈牙利算法？看下：
棋盘黑白染色
相邻格子连边
1*2骨牌对应一条匹配边
这个用特殊字体区分的就是简单思路。
#include<bits/stdc++.h>
#define N 105
#define M 1000005
using namespace std;
struct E{int next,to;}e[M];
int n,m,num,ans;
int h[N*N],mat[N*N];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
bool vis[N*N];
bool tag[N][N];
void add(int u,int v){
e[++num].next=h[u];
e[num].to=v;
h[u]=num;
}
int cal(int x,int y){return(x-1)*n+y;}
bool dfs(int x){
for(int i=h[x];i!=0;i=e[i].next)
if(!vis[e[i].to]){
vis[e[i].to]=1;
if(!mat[e[i].to]||dfs(mat[e[i].to])){
mat[e[i].to]=x;
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
tag[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=4;k++){
int x=i,y=j;
int xx=x+dx[k],yy=y+dy[k];
if(xx<1||xx>n||yy<1||yy>n)continue;
if(tag[x][y]||tag[xx][yy])continue;
add(cal(x,y),cal(xx,yy));
add(cal(xx,yy),cal(x,y));
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i+j)%2){
memset(vis,0,sizeof(vis));
if(dfs(cal(i,j)))ans++;
}
cout<<ans;
return 0;
}
車的放置
题目描述
给定一个N行M列的棋盘，已知某些格子禁止放置。
问棋盘上最多能放多少个不能互相攻击的車。
車放在格子里，攻击范围与中国象棋的“車”一致。
输入格式
第一行包含三个整数N,M,T，其中T表示禁止放置的格子的数量。
接下来T行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
输出格式
输出一个整数，表示结果。
数据范围
1≤N,M≤200
输入样例
8 8 0
输出样例
8
解题思路：
每行每列只能放一个車——所有行、所有列看做两组点某个格子可以放車——格子对应的行、列之间连边放置的車不能互相攻击——选择一组匹配#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
int n,m,t;
const int N=100000;
int head[N],nex[N],to[N],cnt;
bool g[220][220];
int match[N];
bool vis[N];
void init(){
mem(head,-1);
mem(nex,-1);
mem(to,-1);
cnt=0;
mem(match,-1);
mem(vis,false);
mem(g,true);
}
void add(int a,int b){
++cnt;
nex[cnt]=head[a];
head[a]=cnt;
to[cnt]=b;
}
bool dfs(int p){
for (int i=head[p];i!=-1;i=nex[i]){
int y=to[i];
if(vis[y])continue;
vis[y]=true;
if (match[y]==-1||dfs(match[y])){
match[y]=p;
return true;
}
}
return false;
}
int main(){
init();
cin >>n>>m>>t;
while(t--){
int x,y;
cin>>x>>y;
g[x][y]=false;
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (g[i][j]){
add(i,j+n);
add(j+n,i);
}
}
}
int res=0;
for (int i=1;i<=n;i++){
mem(vis,false);
if(dfs(i))res++;
}
cout<<res<<"\n";
return 0;
}
【上机练习】例题：Place the Robots
问题描述
有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、喵地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。
把每一行、每一列被墙隔开，并且包含空地的连续区域称作“块”。
显然，在一个块之中，最多只能放一个机器人。把这些块编上号。
把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。
由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以问题转化为二部图的最大匹配问题。
现在，我们已经基本掌握了二分图的基础算法。让我们接着学习吧！
完备匹配、多重匹配
给定一张二分图，其左部，右部节点数相同，均为N个节点。如果该二分图的最大匹配包含N条匹配边，则称该二分图具有完备匹配。
给定一张包含N个左部节点、M个右部节点的二分图。从中选出尽量多的边。使第i(1≤i≤N)个左部节点至多与kl_i条选出的边相连，第j(1≤j≤M)个右部节点至多与kr_ j条选出的边相连。该问题被称为二分图的多重匹配。
当kl_i=kr_j=1时，二分图的多重匹配即简化为最大匹配。
多重匹配的解决方案
1.拆点：把第i个左部节点拆成kl_i个不同的左部节点，第j个右部节点拆成kr_j个右部节点。对于原图中的每条边(i,j)，在i拆成的所有节点与j拆成的所有节点之间连边。然后求解二分图最大匹配。
2.网络流（想展开讲是不可能的）
例题：导弹防御塔
问题描述
Freda Shi 的城堡遭受了M个入侵者的攻击！
Freda 控制着N座导弹防御塔，每座塔都有足够数量的导弹，但是每次只能发射一枚。每座塔每次发射前需要预热T1秒，发射后需要冷却T2秒。
给定塔和入侵者的坐标。导弹从塔发出直到击中目标所需的飞行时间=塔和入侵者之间的距离。
由于小伙伴 Rainbow Li 就要来拜访她的城堡，Freda 想用最少的时间击退所有的入侵者，请你告诉她一种攻击方案。
输入格式
第一行五个正整数N,M,T1,T2,V。
接下来 M 行每行两个整数，代表入侵者的坐标。
接下来 N 行每行两个整数，代表防御塔的坐标。
输出格式
输出一个实数，表示最少需要多少分钟才能击中所有的入侵者，四舍五入保留六位小数。
数据范围
1≤N,M≤50,坐标绝对值不超过10000，T1,T2,V不超过2000。
输入样例：
3 3 30 20 1 0 0 0 50 50 0 50 50 0 1000 1000 0
输出样例：91.500000
解题思路：最值不容易解决，转化为判定——二分答案T，判定能否在T秒内击退所有入侵者。寻找要素——二分图中的“1”： 每个入侵者被攻击1次后就会被击退。 每座塔可以发射很多次导弹，但是每枚导弹只能攻击1个入侵者。拆点：若某座塔在T秒内可以发射X次导弹，就把这座塔拆成X个点。入侵者、拆点后的导弹分别构成二分图中的左右两部。寻找要素——二分图两部点之间的关系 导弹A在S秒时发射，飞到入侵者B需V秒，若S+V<=T，A到B连边。计算二分图的最大匹配，若每个左部点都能找到匹配，则说明T秒内能击退所有入侵者，可另二分上界r=T，否则令下界l=T+1
Code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=50+10;
struct Node
{
int x,y;
Node() {}
Node(int a,int b):x(a),y(b) {}
} def[maxn],ta[maxn];
int vis[maxn*maxn],pre[maxn*maxn];
double times[maxn][maxn];
double t1,t2,V;
vector<int >G[maxn];
int n,m;
bool DFS(int u)
{
for(int i=0; i<G[u].size(); i++)
{
int v=G[u][i];
if(vis[v])
continue;
vis[v]=1;
if(pre[v]==0||DFS(pre[v]))
{
pre[v]=u;
return true;
}
}
return false;
}
bool judge(double mid)
{
for(int i=1; i<=m; i++)
G[i].clear();
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
{
double now=0;
for(int k=0; k<=m; k++)
{
now=k*(t1+t2);
if(mid-(now+t1+times[i][j])>1e-7)
{
G[i].push_back(j*(m+1)+k-m-1);
}
else
break;
}
}
memset(pre,0,sizeof(pre));
for(int i=1; i<=m; i++)
{
memset(vis,0,sizeof(vis));
if(!DFS(i))
return false;
}
return true;
}
int main()
{
cin>>n>>m>>t1>>t2>>V;
t1/=60.0;
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
ta[i]=Node(x,y);
}
for(int i=1; i<=n; i++)
{
int x,y;
scanf("%d%d",&x,&y);
def[i]=Node(x,y);
}
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
times[i][j]=sqrt((ta[i].x-def[j].x)*(ta[i].x-def[j].x)+(ta[i].y-def[j].y)*(ta[i].y-def[j].y))/V;
double l=0,r=1000000,ans=r;
while(r-l>1e-9)
{
double mid=(l+r)/2.0;
if(judge(mid))
ans=min(ans,mid),r=mid;
else
l=mid;
}
printf("%.6lf\n",ans);
}
二分图最小点覆盖（Minimum Vertex Cover）
König定理
二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数
证明：
首先因为最大匹配是原二分图边集的一个子集，并且所有边都不相交，所以至少需要从每条匹配中选出一个端点。因此最小点覆盖包含的点数不可能小于最大匹配包含的边数。如果能对任意二分图构造出一组点覆盖，其包含的点数等于最大匹配包含的边数，定理即得证。
构造方法
1.求出最大匹配
2.从右部每个未匹配点出发寻找增广路（一定失败），标记访问过的节点。
3.取左部标记点，右部未标记点，构成一组最小覆盖。
经过上述构造方法后，
右部未匹配点一定是标记点——因为它们是出发点
左部未匹配点一定是未标记点——如果被标记(访问)则找到了增广路，矛盾
一对匹配点都被标记或者都未标记——因为左部匹配点只能通过右部到达
取左部标记点、右部未标记点，恰好使得每对匹配点被取走一个
数值上的相等性得证。
匹配边一定被覆盖——每对匹配点取走一个
不存在连接两个未匹配点的边——否则出现仅包含1条边的增广路，矛盾
连接左部匹配点和右部未匹配点的边——后者是出发点，前者一定被标记
连接左部未匹配点和右部匹配点的边——后者未被标记，否则存在增广路
所有边都被覆盖，合法性得证。
例题：Muddy Fields
问题描述
在一块N*M的矩形地面上，有一些格子是泥泞的。
用一些宽为1的木板把泥地盖住，并且不能盖住好地，木板可以重叠。
问最少需要多少木板？ N,M<=50。
解题思路
不能盖住好地，那么宽为1的木板只能放在行、列泥泞块里。
每个泥格子都要被盖住，选择一个块可以盖住一些泥格子。
行、列泥泞块对应左、右部中的点，泥格子对应边。
答案=二分图最小点覆盖。
Code：
#include<bits/stdc++.h>
#define N 1100
int G[N][N], vis[N], used[N];
char maps[N][N];
int m, n, x, y;
bool Find(int u){
int i;
for(i = 1 ; i <= y ; i++){
if(!vis[i] && G[u][i]){
vis[i] = 1;
if(!used[i] || Find(used[i])){
used[i] = u;
return true;
}
}
}
return false;
}
void Build()//构图
{
int i, j, a[N][N] , b[N][N];
x = y = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(i = 1 ; i <= m ; i++)
{
for(j = 1 ; j <= n ; j++)
{
if(maps[i][j] == '*')
{
if(maps[i][j - 1] == '*')
a[i][j] = a[i][j - 1];
else
a[i][j] = ++x;
}
}
}//木板横着放
for(i = 1 ; i <= m ; i++)
{
for(j = 1 ; j <= n ; j++)
{
if(maps[i][j] == '*')
{
if(maps[i - 1][j] == '*')
b[i][j] = b[i - 1][j];
else
b[i][j] = ++y;
G[a[i][j]][b[i][j]] = 1;
}
}
}//木板竖着放
}
int main()
{
int i, j, ans;
while(~scanf("%d%d", &m, &n))
{
ans = 0;
memset(G, 0, sizeof(G));
for(i = 1 ; i <= m ; i++)
{
getchar();
for(j = 1 ; j <= n ; j++)
{
scanf("%c", &maps[i][j]);
}
}
Build();
memset(used, 0, sizeof(used));
for(i = 1 ; i <= x ; i++)//X集合中的点与Y集合中的点找最大匹配
{
memset(vis, 0, sizeof(vis));
if(Find(i))
ans++;
}
printf("%d\n", ans);
}
return 0;
}
二分图最大独立集（Maximum Independent Set）
任意两点在图中都没有边相连的点集称为图的独立集。
定理：二分图最大独立集 = 图的点数 – 二分图最大匹配
证明：选出最多的点构成独立集
在图中去掉最少的点，使剩下的点之间没有边。
用最少的点覆盖所有的边，去掉的是最小覆盖。
例题：骑士放置
问题描述
给定一个N*M的棋盘，有一些格子不能放棋子。问棋盘上最多能放多少个不能互相攻击的骑士（马）。
解题思路：
对棋盘黑白染色，黑、白色的点分别属于左、右部。
可以攻击到的两个格子之间连边。
马沿日字形攻击，所以肯定是在不同颜色的点之间连边。
不能互相攻击，就是寻找一个最大独立集。
Code：
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int N=101;
int n,m,t,ans,fx[N][N],fy[N][N];
bool a[N][N],v[N][N];
co int dx[8]={-2,-2,-1,-1,1,1,2,2};
co int dy[8]={-1,1,-2,2,-2,2,-1,1};
bool dfs(int x,int y){
for(int i=0;i<8;++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>n||ny<1||ny>m||a[nx][ny]||v[nx][ny]) continue;
v[nx][ny]=1;
if(!fx[nx][ny]||dfs(fx[nx][ny],fy[nx][ny])){
fx[nx][ny]=x,fy[nx][ny]=y;
return 1;
}
}
return 0;
}
int main(){
read(n),read(m),read(t);
for(int i=1;i<=t;++i) a[read<int>()][read<int>()]=1;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
if(i+j&1||a[i][j]) continue;
memset(v,0,sizeof v);
ans+=dfs(i,j);
}
printf("%d\n",n*m-t-ans);
return 0;
}
有向无环图的最小路径点覆盖
最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图的所有顶点。(即每个顶点恰好被覆盖一次)
把原图中的每个点拆成二分图中左、右两个点；
对于每条有向边(u,v)，从u的左部点（成为出点）向v的右部点（称为入点）连一条有向边。
最小路径覆盖数 = 原有向图节点数 – 新二分图最大匹配数。
· 不相交的最小路径覆盖->每个点的入度、出度均不超过1
· 拆点转化->二分图每个点连接的边不超过1条->一个匹配
· 有向图路径上的每条边 对应 二分图匹配中的一条匹配边
· 有向图路径上每条边的出点 对应 二分图匹配边的左部点
· 每条路径的最后一个点没有对应
· 最小路径覆盖的路径数 = 最少未匹配的点数 = 原图节点数 – 二分图最大匹配数。
【上机练习】例题：Air Raid
问题描述
N个城市M条道路形成有向无环图。
现在要求派一些伞兵空降在某些城市，然后这些伞兵可以沿着道路访问到其他城市，但是不能有两个或两个以上伞兵访问同一个城市。
问最少需要多少个伞兵。N<=120。
代码不上了。
二分图带权最大匹配（最优匹配）
给定一张二分图，每条边都带有一个权值。求出该二分图的一组最大匹配，使得匹配边的权值总和最大。该问题称为二分图的带权最大匹配，也称最优匹配。
· 二分图带权最大匹配的前提是匹配数最大，然后在最大化匹配边的权值总和。
· 两种解法：KM算法与费用流。
· KM算法只能在满足“带权最大匹配一定是完备匹配”的图中正确求解。
· 不满足时，用最大费用最大流求解。
KM算法
交错树：
在匈牙利算法中，如果从某个左部节点出发寻找匹配失败，那么在DFS的过程中，所有访问过的节点，以及为了访问这些节点而经过的边，共同构成一棵树。这课树的根是一个左部节点，所有叶子节点也都是左部节点（因为最终匹配失败了），并且树上第1,3,5,…层的边都是非匹配边，第2,4,6,…层的边都是匹配边。这棵树称为交错树。
顶标：
在二分图中，给第i(1≤i≤N)个左部节点一个整数值A_i，给第j(1≤j≤N)个右部节点一个整数值B_j。同时，必须满足∀i,j,A_i+B_j≥w(i,j)，其中w(i,j)表示第i个左部点和第j个右部点之间的边权（没有边时设为负无穷）。这些整数值A_i, B_j称为节点的顶标。
· 相等子图
二分图中所有满足节点和A_i+B_j=w(i,j)的边构成的子图，称为二分图的相等子图。
· 若相等子图中存在完备匹配，则这个完备匹配就是二分图的带权最大匹配。
· 证明：
在相等子图中，完备匹配的边权之和等于∑2_(i=1)^N▒〖(A_i+B_j)〗，即所有顶标之和。
因为顶标满足∀i,j,A_i+B_j≥w(i,j)，所以在整个二分图中，任何一组匹配的边权之和都不可能大于所有顶标之和。
KM算法的基本思想就是。先在满足∀i,j,A_i+B_j≥w(i,j)的前提下，给每个节点随意赋值一个顶标，然后采取适当的策略不断扩大相等子图的规模，直至相等子图存在完备匹配。可以赋值A_i=max┬(1≤j≤N)〖{w(i,j)},B_j=0〗
对于一个相等子图，用匈牙利算法求它的最大匹配。若最大匹配不完备，则一定有一个左部节点匹配失败。该节点匹配失败的那次DFS形成了一棵交错树T。
1.除了根节点以外， T中其它的左部点都是从右部点沿着匹配边访问到的，即在程序中调用了dfs(match[y])，其中y是一个右部节点。
2.T中所有的右部点都是从左部点沿着非匹配边访问到的。
在寻找到增广路以前，不会改变已有的匹配，所以一个右部点沿着匹配边能访问到的左部点是固定的。为了让匹配数增加，只能从第2条结论入手，考虑怎样能让左部点沿着非匹配边访问到更多的右部点。
把交错树T中所有的左部节点顶标A_i (i∈T)减小一个整数值∆，把T中所有右部节点顶标B_j (j∈T)增大一个整数值∆：
1.右部点j沿着匹配边，递归访问到i=match[j]：
对于一条匹配边，显然要么i,j∈T(被访问到)，要么i,j∉T(没被访问到)，故A_i+B_j不变，匹配边仍然属于相等子图。
2.左部点i沿着非匹配边，访问右部点j，尝试与之匹配：
因为左部点的访问是被右部点沿着匹配边递归。只需考虑i∈T。
(1) 若i,j∈T, A_i+B_j不变，即以前能从点i访问点j, 现在仍可以。
(2) 若i∈T,j∉T，则A_i+B_j变小，即以前点i访问不到的点j，现在有可能访问到。
为了保证顶标符合前提条件∀i,j,A_i+B_j≥w(i,j)，可在所有的i∈T,j∉T的边(i,j)中，找出最小的A_i+B_j-w(i,j)，作为∆。只要原图存在完备匹配，这样的边一定存在，可以保证至少有一条新的边加入相等子图，使交错树中至少一个左部点能访问到的右部点增多。
不断重复以上过程，直到每一个左部点都匹配成功，就得到了相等子图的完备匹配。即原图的带权最大匹配。
Code：
const int N=105;
int w[N][N]; //边权
int la[N],lb[N];//左右顶点的坐标
bool va[N],vb[N];//访问标记，是否在交错树中
int match[N];//右部点匹配了哪一个左部点
int n,delta;
bool dfs(int x){
va[x]=1; //访问标记，x在交错树中
for (int y=1;y<=n;y++)
if (!vb[y])
if (la[x]+lb[y]-w[x][y]==0){//相等子图
vb[y]=1;//访问标记，y在交错树中
if (!match[y]||dfs(match[y])){
match[y]=x;
return true;
}
}
else delta = min(delta,la[x]+la[y]-w[x][y]);
return false;
}
int KM(){
for (int i=1;i<=n;i++){
la[i]=-(1<<30); //-inf
lb[i]=0;
for (int j=1;j<=n;j++)
la[i]=max(la[i],w[i][j]);
}
for (int i=1;i<=n;i++)
while (true){//直到左部点找到匹配
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
delta = 1<<30; //inf
if (dfs(i)) break;
for (int j=1;j<=n;j++){
if (va[j]) la[j]-=delta;
if (vb[j]) lb[j]+=delta;
}
}
int ans = 0;
for (int i=1;i<=n;i++) ans+=w[match[i]][i];
return ans;
}
【上机练习】例题：Ants
问题描述
平面上共有2*N个点，N个是白点，N个是黑点。对于每个白点，找到一个黑点，把二者用线段连起来，要求最后所有线段都不相交。
解题思路
假定有白点1(a1,b1), 2(a2,b2), 黑点3(a3,b3),4(a4,b4); 如果1(a1,b1)与3(a3,b3)相连，2(a2,b2)与4(a4,b4)相连，如果他们两条边相交，那么dis(1,3)+dis(2,4) 一定大于dis(1,4)+dis(2,3)这两条没有相交的边长和。所以应该连接1-4,2-3; 如果存在满足题目要求的解，那么求一个最小权完美匹配，就可以保证所有匹配的边不相交。
KM算法的几种转化
1.二分图最佳匹配=最小点权覆盖（对偶问题）
2.KM算法是求最大权完备匹配，如果要求最小权完备匹配怎么办？方法很简单，只需将所有的边权值取其相反数，求最大权完备匹配，匹配的值再取相反数即可。
3.KM算法的运行要求是必须存在一个完备匹配，如果求一个最大权匹配(不一定完备)该如何办？依然很简单，把不存在的边权值赋为0。
4.KM算法求得的最大权匹配是边权值和最大，如果我想要边权之积最大，又怎样转化？还是不难办到，每条边权取自然对数，然后求最大和权匹配，求得的结果a再算出ea就是最大积匹配。至于精度问题则没有更好的办法了。
二分图的教程就到此为止了。大家可以回顾一下，欢迎在评论区讨论！
