一、二分图的判定：
如果一张图的N个节点可以分成A，B两个非空集合，其中A∩B＝空集，并且在同一集合内的点之间都没有边相连，那么称这张无向图为一张二分图。A，B分别称为二分图的左部和右部。
定理： 一张无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。
根据该定理，我们可以用染色法进行二分图的判定。大致思想为：尝试用黑白两种颜色标记图中的节点，当一个节点被标记后，它的所有相邻节点应该被标记与它相反的颜色。若标记过程中有冲突，则说明图中存在奇环。二分图染色一般基于深度优先遍历实现，时间复杂度为O（N±M）。
hihoCoder1121 二分图的判定：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=40010;
const int _max=10010;
int head[_max], ver[maxn*2],nt[maxn*2];
int tot;
int ha[_max];
void add(int x,int y)
{
ver[++tot]=y;nt[tot]=head[x];head[x]=tot;
}
bool dfs(int x,int cnt)
{
ha[x]=cnt;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(ha[y]==cnt) return false;
else if(ha[y]==0&&dfs(y,-cnt)==false) return false;
}
return true;
}
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(head,0,sizeof(head));
memset(ha,0,sizeof(ha));
tot=0;
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
bool flag=true;
for(int i=1;i<=n;i++)
{
if(ha[i]==0)
if(dfs(i,1)==false)
{
flag=false;
break;
}
}
if(flag) printf("Correct\n");
else printf("Wrong\n");
}
return 0;
}
二、二分图最大匹配：
任意两条边都没有公共端点 的边的集合被称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。
对于任意一组匹配S（S是一个边集），属于S的边被称为匹配边，不属于S的边被称为非匹配边。
匹配边的端点被称为匹配点，其他节点被称为非匹配点。
如果在二分图中存在一条连接两个非匹配点的路径path，使得非匹配边与匹配边在path上交替出现，那么称path是匹配S的增广路，也称交错路。
增广路显然具有以下性质：
（1） 长度len是奇数。
（2）路径上第1，3，5……len条边是非匹配边，第2，4，6，……len-1条边是匹配边。
正因为以上性质，如果我们把路径上所有边的状态取反，原来的匹配边变成非匹配的，原来的非匹配边变成匹配的，那么得到的新边集SS仍然是一组匹配，并且匹配边数增加了1。进一步可以得到推论：
二分图的一组匹配S是最大匹配，当且仅当图中不存在S的增广路。
匈牙利算法（增广路算法）：
匈牙利算法，又称增广路算法，用于计算二分图的最大匹配。它的主要过程为：
（1）设S为空集，即所有边都是非匹配边。
（2）寻找增广路path，把路径上所有边的匹配状态取反，得到一个更大的匹配SS。
（3）重复第二步，直至图中不存在增广路。
该算法的关键在于如何找到一条增广路。匈牙利算法依次尝试给每一个左部节点x寻找一个匹配的右部节点y。右部点y能与左部点x匹配，需要满足以下两个条件之一：
（1）y本身就是非匹配点。
此时无向边（x，y）本身就是非匹配边，自己构成一条长度为1的增广路。
（2）y已经与左部点xx匹配，但是从xx出发能找到另一个右部点yy与之匹配。
此时路径x–y--xx–yy为一条增广路。
在实际的程序实现中，我们采用深度优先搜索的框架，递归地从x出发寻找增广路。若找到，则在深搜回溯时，正好把路径上的匹配状态取反。另外，可以用全局bool数组标记节点的访问情况，避免重复搜索。
匈牙利算法的正确性基于贪心策略，它的一个重要特点时：当一个节点称为匹配点后，至多因为找到增广路而更换匹配对象，但是绝对不会再变回非匹配点。
对于每个左部节点，寻找增广路最多遍历整张二分图一次。因此，该算法的时间复杂度为O（NM）。
bool dfs(int x)
{
for(int i=head[x],y;i;i=nt[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++;
}
hihoCoder1122 二分图最大匹配：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
const int _max=1005;
const int maxn=10005;
int head[_max],ver[maxn],nt[maxn];
int match[_max];
bool ha[_max];
int tot;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
bool dfs(int x)
{
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(!ha[y])
{
ha[y]=true;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return true;
}
}
}
return false;
}
int main(void)
{
tot=0;
memset(head,0,sizeof(head));
memset(match,0,sizeof(match));
int n,m;
int ans=0;
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
{
memset(ha,0,sizeof(ha));
if(dfs(i)) ans++;
}
printf("%d\n",ans/2);//注意此处除以2。
return 0;
}
Hopcroft-karp：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
using namespace std;
const int maxn=5050;
const int inf=0x7fffffff;
int head[maxn]={0},ver[maxn*2],nt[maxn*2];
int dis,nx,ny,dx[maxn],dy[maxn],mx[maxn],my[maxn];
bool ha[maxn];
int tot=0;
int n,m;
void add(int x,int y)
{
ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
ver[++tot]=x,nt[tot]=head[y],head[y]=tot;
}
bool searchp(void)
{
queue<int>q;
dis=inf;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=1;i<=nx;i++)
{
if(mx[i]==-1)
{
q.push(i);
dx[i]=0;
}
}
while(q.size())
{
int x=q.front();
q.pop();
if(dx[x]>dis) break;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(dy[y]==-1)
{
dy[y]=dx[x]+1;
if(my[y]==-1) dis=dy[y];
else
{
dx[my[y]]=dy[y]+1;
q.push(my[y]);
}
}
}
}
return dis!=inf;
}
bool dfs(int x)
{
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
if(!ha[y]&&dy[y]==dx[x]+1)
{
ha[y]=true;
if(my[y]!=-1&&dy[y]==dis) continue;
if(my[y]==-1||dfs(my[y]))
{
my[y]=x;mx[x]=y;
return true;
}
}
}
return false;
}
int maxmatch(void)
{
int res=0;
memset(mx,-1,sizeof(mx));
memset(my,-1,sizeof(my));
while(searchp())
{
memset(ha,0,sizeof(ha));
for(int i=1;i<=nx;i++)
if(mx[i]==-1&&dfs(i))
res++;
}
return res;
}
int main(void)
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
nx=n;
printf("%d\n",maxmatch()/2);
return 0;
}
二分图匹配模型：
两个要素：
（1）节点能分成独立的两个集合，每个集合内部有0条边。
（2）每个节点只能与1条匹配边相连。
我们把它简称为 0要素 和 1要素。稍后的例题中会具体题目进行分析。
三、二分图其他：
完备匹配： 给定一张二分图，其左部，右部节点数相同，均为N个节点。如果该二分图的最大匹配包含N条匹配边，则称该二分图具有完备匹配。
多重匹配： 给定一张包含N个左部节点，M个右部节点的二分图。从中选出尽量多的边，使第i（1≤i≤N）个左部节点至多与kli条选出的边相连，第j（1≤j≤M）个右部节点至多与krj条选出的边相连。该问题被称为二分图的多重匹配。
当 kli = krj = 1时，上述问题就简化为二分图的最大匹配。因此，多重匹配时一个广义的 “匹配” 问题，每个节点可以与不止一条 “匹配” 边相连，但不能超过一个给定的限制。
多重匹配一般有四种解决方案：
（1）拆点。把第i个左部点拆成 kli 个不同的左部节点，第j个右部节点拆成 krj 个右部节点。对于原图中的每条边（i，j），在 i 拆成的所有节点与 j 拆成的所有节点之间连边。然后求解二分图的最大匹配。
（2）如果所有的 kli = 1，或者所有的 krj = 1，即只有一侧是多重匹配，不妨设左部是多重的，那么可以直接在匈牙利算法中让每个左部节点执行kli次dfs。
（3）在第二种方案中，当然也可以交换左右两部，设 “右部” 是多重的，修改匈牙利算法的实现，让右部节点可以匹配krj次，超过匹配次数后，就要依次尝试递归当前匹配的krj个左部节点，看能否找到增广路。
（4）网络流。这是最一般也是最高效的解决方法，我将稍后学习。
四、二分图带权匹配：
给定一张二分图，二分图的每条边都带有一个权值。求出该二分图的一组最大匹配，使得匹配边的权值总和最大。这个问题被称为二分图的带权最大匹配，也称二分图最有匹配。注意：二分图带权最大匹配的前提是匹配数最大，然后再最大化匹配边的权值总和。
二分图带权最大匹配有两种解法：费用流和KM算法。先学习KM 算法，费用流将在稍后学习。
KM算法的程序实现简单，在稠密图上的效率一般高于费用流。不过KM算法有很大的局限性，只能在满足 带权最大匹配一定是完备匹配的图中正确求解。所以一般情况下，应采用费用流来计算二分图的带权最大匹配。
在以下KM算法中，我们假设二分图左、右两部的节点数均为N。
交错树：
在匈牙利算法中，如果从某个左部节点出发寻找匹配失败，那么在DFS的过程中，所有访问过的节点，以及为了访问这些节点而经过的边，共同构成一棵树。
这棵树的根是一个左部节点，所有叶子节点也都是左部节点（因为最终匹配失败了），并且树上第1，3，5……层的边都是非匹配边，第2，4，6……层的边都是匹配边。因此，这棵树被称为交错树。
顶标：
全称 顶点标记值 。在二分图中，给第 i （1≤i≤N）个左部节点一个整数值Ai，给第 j （1≤j≤N）个右部节点一个整数值Bj。同时，必须满足所有的 i，j ----Ai+Bj≥w（i，j），其中 w（i，j）表示第 i 个左部点与第 j 个右部点之间的边权（没有边时设为负无穷）。这些整数值Ai，Bj称为节点的顶标。
相等子图：
二分图中所有节点和Ai+Bj=w（i，j）的边构成的子图，称为二分图的相等子图。
定理： 若相等子图中存在完备匹配，则这个完备匹配就是二分图的带权最大匹配。
证明：
在相等子图中，完备匹配的边权之和等于（Ai + Bi）（1≤i≤N）的和，即所有顶标之和。
因为顶标满足Ai+Bj≥w（i，j），所以在整个二分图中，任何一组匹配的边权之和都不可能大于所有的顶标的和。
KM算法的基本思想就是：先在满足所有 Ai + Bj ≥ w（i，j）的前提下，给每个节点随意赋值一个顶标，然后采取适当的策略不断扩大相等子图的规模，直至相等子图存在完备匹配。例如我们可以赋值 Ai = max{ w（i，j）}，（ i 到 j 的所有边），Bj=0。
对于一个相等子图，我们用匈牙利算法求出它的最大匹配。若最大匹配不完备，则说明一定有一个左部节点匹配失败。该节点匹配失败的那次DFS形成了一棵交错树，即为T。
考虑匈牙利算法的流程，容易发现以下两条结论：
（1）除了根节点以外，T中其他的左部点都是从右部点沿着匹配边访问到的，即在程序中调用了dfs（match（y）），其中y是一个右部节点。
（2）T中所有的右部点都是从左部点沿着非匹配边访问到的。
在寻找到增广路以前，我们不会改变已有的匹配，所以一个右部点沿着匹配边能访问到的左部点是固定的。为了让匹配数增加，我们只能从第二条结论入手，考虑 怎样能让左部点沿着非匹配边访问到更多的右部点。
假设我们把交错树T中的所有左部节点顶标 Ai （i∈T）减小一个整数值▲，把T中的所有右部节点顶标 Bj （j∈T）增大一个整数值▲，节点的访问情况会有哪些变化？
我们分两方面进行讨论：
（1）右部点 j 沿着匹配边，递归访问 i = match （j） 的情形。
对于一条匹配边，显然要么 i，j∈T（被访问到），要么 i，j 不属于T（没被访问到）。故 Ai + Bj 不变，匹配边仍然属于相等子图。
（2）左部点 i 沿着非匹配边，访问右部点 j ，尝试与之匹配的情形。
因为左部点的访问是被动的（被右部点沿着匹配边递归），所以只需要考虑 i ∈T。
若 i， j ∈ T，则Ai + Bj 不变。
即以前能从 i 访问到的点 j ，现在仍能访问。
若 i ∈T ， j 不属于 T，则Ai+Bj减小。
即以前从 i 访问不到的点 j ，现在有可能访问到了。
为了保证顶标符合前提条件 所有 Ai + Bj ≥ w（i，j），我们就在所有 i∈T，j不属于T的边（i，j）之中，找出最小的Ai + Bj - w（i，j） 最为▲值。只要原图存在完备匹配，这样的边一定存在。上述方法既不会破坏前提条件，又能保证至少有一条新的边会加入相等子图，使交错树中至少一个左部点能访问到的右部点增多。
不断重复以上过程，直到每一个左部点都匹配成功，就得到了相等子图的完备匹配，即原图的带权最大匹配。具体实现时，▲的值可以在DFS的过程中顺便求出。KM算法的时间复杂度为O（N * N * N）。
const int maxn=105;
int w[maxn][maxn];//边权
int la[maxn],lb[maxn];//左、右部点的顶标
bool va[maxn],vb[maxn];//访问标记：是否在交错树中
int match[maxn];//右部点匹配了哪一个左部点
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]+lb[y]-w[x][y]);
}
return false;
}
int KM(void)
{
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;
}
slack对完全图有些许优化：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=310;
const int inf=0x3f3f3f3f;
int nx,ny;
int g[maxn][maxn];
int linker[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool visx[maxn],visy[maxn];
bool dfs(int x)
{
visx[x]=true;
for(int y=0;y<ny;y++)
{
if(visy[y]) continue;
int temp=lx[x]+ly[y]-g[x][y];
if(!temp)
{
visy[y]=true;
if(linker[y]==-1||dfs(linker[y]))
{
linker[y]=x;
return true;
}
}
else slack[y]=min(slack[y],temp);
}
return false;
}
int KM(void)
{
memset(linker,-1,sizeof(linker));
memset(ly,0,sizeof(ly));
for(int i=0;i<nx;i++)
{
lx[i]=-inf;
for(int j=0;j<ny;j++)
lx[i]=max(lx[i],g[i][j]);
}
for(int x=0;x<nx;x++)
{
for(int i=0;i<ny;i++)
slack[i]=inf;
while(true)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(dfs(x)) break;
int d=inf;
for(int i=0;i<ny;i++)
{
if(!visy[i]) d=min(d,slack[i]);
}
for(int i=0;i<nx;i++)
if(visx[i]) lx[i]-=d;
for(int i=0;i<ny;i++)
{
if(visy[i]) ly[i]+=d;
else slack[i]-=d;
}
}
}
int res=0;
for(int i=0;i<ny;i++)
if(linker[i]!=-1)
res+=g[linker[i]][i];
return res;
}
int main(void)
{
int n;
while(scanf("%d",&n)!=EOF)
{
nx=ny=n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&g[i][j]);
printf("%d\n",KM());
}
return 0;
}
京公网安备 11010502036488号