二分图最大匹配(hungary正向表形式)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】二分图最大匹配(hungary正向表形式)

作者:沅泽 / 发布于2016/2/23/ 697

//二分图最大匹配,hungary算法,正向表形式,复杂度O(m*e)
//返回最大匹配数,传入二分图大小m,n和正向表list,buf(只需一边)
//match1,match2返回一个最大匹配,未匹配顶点match值为-1
#include <string.h>
#define MAXN 310
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)

int hungary(int m,int n,int* list,int* buf,int* match1,int* match2){
	int s[MAXN],t[MAXN],p,q,ret=0,i,j,k,l;
	for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
		for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
			for (l=list[k=s[p]];l<list[k+1]&&match1[i]<0;l++)
				if (t[j=buf[l]]<0){
					s[++q]=match2[j],t[j]=k;
					if (s[q]<0)
						for (p=j;p>=0;j=p)
							match2[j]=k=t[j],p=match1[k],match1[k]=j;
				}
	return ret;
}

试试其它关键字

　二分图　　正向表　

同语言下

.C分鱼问题
.链表
.最大连续和
.编码字符串
.libiconv字符编码处理及判断字符串是否为utf8
.一组数中两两二元组，差最大有几对，差最小呢？（数组
.通过管道获取一个进程的执行状态
.多关键字排序
.字符串字典序排序
.3元一次方程(牛顿迭代法求方程的根)

可能有用的

.C#实现的html内容截取
.List 切割成几份工具类
.SQL查询多列合并成一行用逗号隔开
.一行一行读取txt的内容
.C#动态修改文件夹名称(FSO实现，不移动文件)
.c# 移动文件或文件夹
.c#图片添加水印
.Java PDF转换成图片并输出给前台展示
.网站后台修改图片尺寸代码
.处理大图片在缩略图时的展示

沅泽贡献的其它代码(20)

.在浏览器状态栏显示访问者在本页停留的时间
.移动端开发图片自适应高度和自动全屏
.md5加密
.用字符串创建列表
.iOS safari 如何阻止“橡皮筋效果”？
.ajax解析json数据
.判线性相关(正交化)
.Asp.net MVC 使用json数据格式交互示例
.二分图最大匹配(hungary正向表形式)
.判断指定id的对象是否存在