二分图的概念:二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。
匹配:在图论中,一个匹配是一个边的集合,其中任意两条边都没有公共顶点。
最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。
交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点,则这条交替路称为增广路。
增广路有个重要特点就是:未匹配边数比匹配边数多一,这样就可以让未匹配边和匹配边身份交换使得匹配边数加一,所以一直寻找增广路来增加匹配数,直到找不到增光路为止。
代码实现(Dfs):
struct Edge
{
int from;
int to;
};
vector <int> G[max];//存储i点的出发点编号
int matchingnode[max];
int check[max];
int Dfs(int u)
{
vector <int>::iterator it;
for(it=G[u].begin();it!=G[u].end();it++)
{
int v=*it;
if(!check[v])//判断是否在交替路中
{
check[v]=1;
if(matchingnode[v]==-1||Dfs(matchingnode[v]))//是否是匹配点
{
matching[v]=u;
matching[u]=v;
return 1;
}
}
}
return 0;
}
int hungarian ()
{
int _count;
memset(matchingnode,-1,sizeof(matchingnode));
for(int i=0;i<max;i++)
{
if(matchingnode[i]==-1)
{
memset(check,0,sizeof(check));
if(Dfs(i))
_count++;
}
}
return _count;
}