• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C语言[二分图最大匹配] 匈牙利算法

OC/C/C++ 水墨上仙 2672次浏览

C语言[二分图最大匹配] 匈牙利算法

const int INF = 0x3f3f3f3f; 
const int MAXN=510;
int uN,vN;//u,v数目
int g[MAXN][MAXN];//构图
int link[MAXN];   //link[v]=u表示右边对左边的匹配
bool used[MAXN];//是否访问过
bool dfs(int u)//从左边开始找增广路径
{
    int v;
    for(v=0;v<vN;v++)//右边顶点编号从0开始
	{
		if(g[u][v]&&!used[v])  //如果存在通路,且从u开始搜索时该点没访问过
		{
			used[v]=true;
			if(link[v]==-1 || dfs(link[v]))	//找增广路
			{
				link[v]=u;
				return true;
			}
		}
	}
    return false;
}
int hungary()
{
    int res=0;
    int i,u;
    memset(link,-1,sizeof(link));
    for(u=0;u<uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u)) 
			res++;
    }
    return res;
}   

以上是匈牙利算法的关键代码
其实实现就是一个找增广路径的过程
增广路径&nbsp字面意思就是把路径越增越广
实际意思也是一样的
DFS从左边起始点开始搜索
1.右边如果没匹配就匹配(link[v]==-1)
2.如果右边匹配过了…就从右边点找左边的匹配点再搜索看是否能增广

以上两种情况都能使匹配边+1

这就是找二分图最大匹配的最简单算法了,代码很短,时间复杂度为O(n^3),网络流当然也能实现咯…

记住咯:&nbsp
最小点覆盖&nbsp=&nbsp二分图最大匹配
最小路径覆盖&nbsp=&nbsp|P|&nbsp-&nbsp二分图最大匹配

PS:网络流还没看…悲剧…滚去看DINIC了…


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C语言[二分图最大匹配] 匈牙利算法
喜欢 (0)
加载中……