二分图匹配相关算法_除以零_的博客-程序员秘密_二分图匹配算法有哪些

技术标签: 模板  

二 分 图 匈 牙 利 算 法 二分图匈牙利算法
这里简单记录下二分图匹配的相关算法,供自己使用。如果各位游客看到觉得浪费时间,便请移步,文章全为个人模板记录

  • 匈牙利算法
    匈牙利算法研究的是二分图的最大匹配,是对给定的二分图求得最大的满足条件的匹配数,匹配对。其算法思想是利用Berge定理和Hall定理将初始匹配通过迭代寻找增广路径得到最大匹配,每次迭代得到的匹配大小加1
    具体迭代实现有DFS和BFS两种。下面贴上DFS版的cpp写法
    时间复杂度O( n × m n \times m n×m)
//匈牙利算法 时间复杂度为O(n*m)
#include "bits/sdtc++.h"
#define MAX 1003

using namespace std;
int n,m,e;
int map[MAX][MAX];
int vis[MAX];
int nextLeft[MAX],nextRight[MAX];//nextLeft[]是左部点匹配到右边的点,同理nextRight
int fa[MAX];

bool Find(int u) {
    			//是DFS迭代寻找增广路径,(还有个形象的说法就是腾地)
	for (int i = 1; i<= m; i++) {
    
		if (map[u][i] && !vis[i]) {
    
			vis[i] = 1;
			if (-1==nextRight[i] || Find(nextRight[i])) {
    	//“腾地”,如果,nextRight[i]还未匹配右边的点,或者nextRight[i]还有增广路径可走有其他点可以与其匹配就“腾地”
				nextRight[i] = u;
				nextLeft[u] = i;
				return true;
			}
		}
	}
	return false;
}

int MaxMatch() {
    		//最大匹配,在主函数中直接调用MaxMatch(),返回最大匹配数。
	int ans(0);
	memset(nextLeft,-1,sizeof(nextLeft));
	memset(nextRight,-1,sizeof(nextRight));
	for (int i = 1; i<=n; i++) {
    
		if (-1 == nextLeft[i]) {
    
		// {
    
			memset(vis,0,sizeof(vis));
			if (Find(i))	ans++;
		}
	}
	return ans;
}


int main(int argc,char *argv[]) {
    
	scanf("%d%d%d", &n,&m,&e);
	for (int i = 1; i <= e; i++) {
    
		int u,v;
		scanf("%d%d", &u,&v);
		if (u>=1&&u<=n&&v>=1&&v<=m) {
    
			map[u][v] = 1;
		}
	}
	printf("%d\n", MaxMatch());
	return 0;
}

H o p c r o f t − K a r p 算 法 Hopcroft-Karp 算法 HopcroftKarp
该算法也是求二分图最大匹配的,不过相对与匈牙利算法而言,效率更高,时间复杂度更优秀,但缺点是书写麻烦。

  • Hopcroft-Karp 算法
    HK算法相比匈牙利算法高效的地方在于寻找增广路上,匈牙利算法是每次迭代的时候寻找一条增广路,而HK算法是先寻找一个增广路集合,在一次搜索中寻找多条不相交的增广路径,形成极大增广路径集。
    HK算法的复杂度 O( n 1 2 × m n^{\frac{1}{2}}\times m n21×m)
    主函数直接调用MaxMatch().
//Hopcroft-Karp 算法 时间复杂度为O(n^(1/2)*m)
//该算法是对匈牙利算法的优化,利用匈牙利算法一次只能找到一条增广路径,
//Hopcroft-Karp就提出一次找到多条不相交的增广路径(不相交就是没有公共点和公共边的增广路径),称为增广路集
//然后根据这些增广路径添加多个匹配,并逐渐增加增广路径集中增广路径的长度。
#include "bits/stdc++.h"
#define MAX 3003
#define INF 0x3f3f3f3f

using namespace std;
int nextLeft[MAX],nextRight[MAX];	//nextLeft[MAX]是左集合匹配右集合的点,同理nextRight也是
int dLeft[MAX],dRight[MAX];			//dLeft[MAX],dRight[MAX]是增广路径长度,或者说BFS深度
int dx[MAX],dy[MAX];
int map[MAX][MAX];					//map[MAX][MAX]存图
int nx,ny;							//nx,ny分别是左集合点个数,右集合点个数
int dis;							
int vis[MAX];						//标记数组.

bool searchPath() {
    					//寻找增广路径集,其增广路径集中每条增广路径长度一样
	queue<int>Q;
	dis = INF;
	memset(dLeft,-1,sizeof(dLeft));
	memset(dRight,-1,sizeof(dRight));
	for (int i = 1;i <= nx; i++) {
    	//在BFS中宽度搜索
		if (-1 == nextLeft[i]) {
    	//将未遍历的节点 入队 并初始化次节点距离为0 
			Q.push(i);
			dLeft[i] = 0;
		}
	}
	while (!Q.empty()) {
    			//广度搜索增广路径
		int u = Q.front();
		Q.pop();
		if (dLeft[u] > dis)	break;
		for (int v = 1; v <= ny; v++) {
    	//取右侧节点 
			if (map[u][v] && -1==dRight[v]) {
    	//右侧节点的增广路径的距离
				dRight[v] = dLeft[u]+1;			//v对应的距离 为u对应距离加1
				if (-1 == nextRight[v])	dis = dRight[v];
				else {
    
					dLeft[nextRight[v]] = dRight[v]+1;
					Q.push(nextRight[v]);
				}
			}
		}
	}
	return dis != INF;
}
bool Find(int u) {
    				//Find函数,对增广路径集进行增广。
	for (int v = 1; v <= ny; v++) {
    
		if (!vis[v] && map[u][v] && dRight[v] == dLeft[u]+1) {
    
			vis[v] = 1;
			if (nextRight[v] != -1 && dRight[v] == dis)	continue;
			if (-1 == nextRight[v] || Find(nextRight[v])) {
    
				nextRight[v] = u;nextLeft[u] = v;
				return true;
			}
		}
	}
	return false;
}
int MaxMatch() {
    
	int ans(0);
	memset(nextRight,-1,sizeof(nextRight));
	memset(nextLeft,-1,sizeof(nextLeft));
	while(searchPath()) {
    		//不断进行增广路径集的操作,其增广路径也不断增长。
		memset(vis,0,sizeof(vis));
		for (int i = 1; i <= nx; i++) {
    
			if (-1 == nextLeft[i]) {
    
				if (Find(i))	ans++;
			}
		}
	}
	return ans;
}

int main(int argc,char *argv[]) {
    
	// int n,m,e;
	int e;
	scanf("%d%d%d", &nx,&ny,&e);
	for (int i = 1; i <= e; i++) {
    
		int u,v;
		scanf("%d%d", &u,&v);
		if (u>=1&&u<=nx&&v>=1&&v<=ny) {
    
			map[u][v] = 1;
		}
	}
	printf("%d\n", MaxMatch());
	return 0;
}

二 分 图 多 重 匹 配 二分图多重匹配

  • 多重匹配算法
    二分图普通的匹配是一对一的匹配,左集合X和右集合Y是一一对应的关系,如果允许Y集合中的一个元素和集合X中的多个元素匹配(通常有一个最大限制n),但是X集合中的一个元素只能和Y集合的一个元素匹配,这就是二分图多重匹配的模型
  • 算法步骤
    在构造二分图的多重匹配模型时,由于集合Y中的一个元素可以同时匹配集合X中的多个元素。所以,匈牙利算法中的cy[MAX]应该更换为一个二维数组 cy[MAX][MAX]。cy[i][j],表示与元素 y i y_i yi匹配的第j个元素,同时用vcy[i]来记录与元素 y i y_i yi匹配的元素的数量。
    二分查找可以构成多重匹配的limit值。在主函数main()方法中进行二分查找,并调用MulMatch()就可以得到limit值。
/*二分图多重匹配算法*/
#include "bits/stdc++.h"

#define MAX 1001
int bmap[MAX][MAX];
int vis[MAX];
int nx,ny;
int vcy[MAX];
int cy[MAX][MAX];
int limit;
int left;int right;

bool Find(int u) {
    
	for (int i = 1; i <= ny; i++) {
    
		if (bmap[u][i] && !vis[i]) {
    
			vis[u] = 1;
			if (vcy[i] < limit) {
    
				cy[i][vcy[i]++] = u;
				return true;
			}
			for (int j = 1; j <= vcy[i]; j++) {
    
				if (Find(cy[i][j])) {
    
					cy[i][j] = u;
					return true;
				}
			}
		}
	}
	return false;
}
bool MulMatch() {
    
	memset(vcy,0,sizeof(vcy));
	for (int i = 1; i <= nx; i++) {
    
		memset(vis,0,sizeof(vis));
		if (!Find(i))	return false;
	}
	return true;
}

using namespace std;

int main(int argc,char *argv[]) {
    
	/*
		根据题意建图...
	*/
	left = 0, right = nx;		//二分查找
	while (left < right) {
    
		limit = (left+right)/2;
		if (MulMatch())	right = limit;
		else			left = limit+1;
	}
	/*
		根据题意输出...
	*/
	return 0;
}

二 分 图 最 佳 匹 配 二分图最佳匹配

  • Kuhn-Munkres算法
/*二分图最佳匹配算法*/
/*Kuhn-Munkres算法*/
/*hdu 2255 例题*/

#include "bits/stdc++.h"
#define MAX 1001
#define INF 0x3f3f3f3f

using namespace std;

int bmap[MAX][MAX];
int visx[MAX],visy[MAX],cx[MAX],cy[MAX];
int nextLeft[MAX],nextRight[MAX];
int w[MAX][MAX];
int n,m,ans;	//n左m右

bool Find(int x) {
    
	visx[x] = 1;
	for (int i = 1; i <= m; i++) {
    
		if (!visy[i] && (cx[x]+cy[i] == w[x][i])) {
    
			visy[i] = 1;
			if (!nextRight[i] || Find(nextRight[i])) {
    
				nextRight[i] = x;
				nextLeft[x] = i;
				return true;
			}
		}
	}
	return false;
}
int kuhnMunkres() {
    
	for (int i = 1; i <= n; i++) {
    
		while (1) {
    
			int D = INF;
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			if (Find(i))	break;
			for (int j = 1; j <= n; j++) {
    
				if (visx[j])	
					for (int k = 1; k <= m; k++)
						if (!visy[k])	D = min(D,cx[j]+cy[k]-w[j][k]);
			}
			if (D == INF)	return -1;
			for (int j = 1; j <= n; j++)
				if (visx[j])	cx[j] -= D;
			for (int j = 1; j <= m; j++) 
				if (visy[j])	cy[j] += D;
		}
	}
	ans = 0;
	for (int i = 1; i <= m; i++)
		ans += w[nextRight[i]][i];
	return ans;
}

int main(int argc, char const *argv[]) {
    
	while (scanf("%d", &n)!=EOF) {
    
		m = n;
		memset(cy,0,sizeof(cy));
		memset(cx,0,sizeof(cx));
		memset(w,0,sizeof(w));
		for (int i = 1; i <= n; i++) {
    
			int D = 0;
			for (int j = 1; j <= m; j++) {
    
				scanf("%d", &w[i][j]);
				D = max(D,w[i][j]);
			}
			cx[i] = D;
		}
		memset(nextLeft,0,sizeof(nextLeft));
		memset(nextRight,0,sizeof(nextRight));
		int ANS = kuhnMunkres();
		printf("%d\n", ANS);
	}
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/SuperBvs/article/details/87926957

智能推荐

Zabbix使用命令总结_꧁刘向洋꧂的博客-程序员秘密_zabbix启动命令

一、yum安装方式四个服务分别是数据库、zabbix-server、httpd、zabbix-agent[[email protected] ~]# systemctl start mariadb #启动mariadb[[email protected] ~]# systemctl enable mariadb #开机时启动mariadb[[email protected] ~]# system...

python基础学习(5)——超详细字符串常用操作_徕胖的博客-程序员秘密

(1)创建字符串#字符串引号#双引号和单引号无区别,但文本中有引号时,需要相互交替使用str1 = 'abc'str2 = 'abc'str3 = "'你好呀'!"#字符串中包含单引号str4 = '"你好"!' #字符串中包含双引号print(str3)print(str4)#需要多行字符串时,使用三引号(2)转义字符#使用反斜杠\转义字符print('\\') #\print('\'') #'(3)格式化字符串#格式化字符串:在字符串中插入变量name

算法面试必备-----手撕代码高频题_Avery123123的博客-程序员秘密_手撕代码是给题目链接吗

算法面试必备-----手撕代码高频题算法面试必备-----手撕代码高频题字节跳动阶乘末尾0的个数判断一颗二叉树是否为镜像对称算法面试必备-----手撕代码高频题字节跳动阶乘末尾0的个数输入描述:输入为一行,n(1 ≤ n ≤ 1000)输出描述:输出一个整数,即题目所求解法:要判断末尾有几个0就是判断可以整除几次10。10的因子有5和2,而在0~9之间5的倍数只有一个,2的倍数相对较多,所以本题也就转换成了求N阶乘中有几个5的倍数。也就是每多出来一个5,阶乘末尾就会多出来一个0,这样n /

angularjs ng-click无效的可能原因_wanyangnumberone的博客-程序员秘密

在uigrid里面使用celltemplate嵌入的按钮,使用ng-click点击不能打开新页面,需要增加grid.appScope.具体的函数名切换scope才可以错误例子:cellTemplate: '' +' onShelf(\'\',\'onShelf.html\',\'on\',row.entity)"  class="btn btn-danger btn-xs btn-sm

网易云课堂学习笔记——带参数的构造函数以及类内声明类外写函数的方法_DJAlove的博客-程序员秘密_类外函数类内声明参数

#include &amp;lt;iostream&amp;gt;using namespace std;//带参数的构造函数,带有参数的构造函数在声明对象的时候一定要把参数传进来//或者可以直接在构造函数中初始化,这样不传参数也可以//构造函数之间也可以构成重载关系,只需要用传入参数的不同来判断既可class cstu{public: int age; char name; /*cstu(int a,char ...

网页div元素导出成图片 JS+html2canvas_岗少的博客-程序员秘密

将html的元素转换成图片,并将该图片下载到本地的几种方法。

随便推点

App免邀请码安装_Xinstall渠道统计的博客-程序员秘密

相较于营销推广,邀请好友机制显然获客的预算成本低得多。另外,邀请的优点不仅在于引流新用户,在邀请时无形中也增强了老用户对产品的认同感和活跃度。简单来说,这是产品低成本拉新促活的不二之选。涉及到一个邀请层级绑定的问题,邀请活动要让新用户填写信息,由于在操作系统层面,iOS 和 Android 在数据来源获取上有各自的限制,导致统计数据不够精准,因此在技术不成熟的早期,大部分 App 只能通过让用户填写一些唯一标识上报平台方,来确认邀请人和被邀请人身份。邀请码就是一串无序的乱码,邀请人生成时会被系统获取,

2022年物理学诺奖获主,他们证明爱因斯坦错了_小麦大叔的博客-程序员秘密

点击上方“小麦大叔”,选择“置顶/星标公众号”福利干货,第一时间送达2022年诺贝尔物理学奖获得者:法国物理学家阿兰·阿斯佩(Alain Aspect)、美国理论和实验物理学家约翰克·劳瑟(John F. Clauser) 和奥地利物理学家安东·塞林格(Anton Zeilinger)今年诺贝尔物理学奖正式揭晓。瑞典斯德哥尔摩当地时间10月4日中午11时45分(北京时间17时45分),瑞典皇家科学...

使用NetMHCpan进行肿瘤新抗原预测分析_生信修炼手册的博客-程序员秘密

欢迎关注”生信修炼手册”!NetMHCpan软件用于预测肽段与MHC I型分子的亲和性,最新版本为v4.0, 基于人工神经网络算法,以180000多个定量结合数据和MS衍生的MHC洗脱配...

博客的开始,介绍一些自己,我是这样的一个程序员_qihailei1118的博客-程序员秘密

我是一个性格开朗的程序员,求知欲望强烈,喜欢专研编程的东西,认为自己的逻辑思维还行。我也喜欢从不同的角度考虑问题,解决问题的能力强;有很好的语言表达能力和沟通协作能力;对事、对工作认真、负责;对生活积极向上,时间观念强烈。  在项目组中,能够很好的进行技术的沟通,并能很好的接受先进的设计思想和思路,对整个项目开发进度有很强的时间观念,对完成任务的责任心非常强。  以前做过的一个:客户关系管

华为云服务器新增d盘,华为桌面云【windows组策略】桌面重定向_weixin_39629617的博客-程序员秘密

参考文档,可以设置组策略,将计算机的桌面,我的文档 等文件夹放置在 D盘或者其他盘windows域工作模式客户端文件夹重定向实现1.需求说明:在普通的域工作模式下用户的数据保存在本地客户端,需要查看数据时只能去固定的机器查看,域模式下的文件夹重定向使得我们可以将自己的某些数据保存在固定的远端服务器,自己登录域内的任何一个机器都会看到自己的数据,就像在自己的计算机登录一样。这种设置相当于漫游一样,将...

SpringBoot_线程池_ThreadPoolTaskExecutor_尼古拉斯__赵四的博客-程序员秘密

1. 线程池配置import org.springframework.context.annotation.Bean;import org.springframework.context.annotation.Configuration;import org.springframework.scheduling.concurrent.ThreadPoolTaskExecutor;

推荐文章

热门文章

相关标签