Java教程

匈牙利算法

本文主要是介绍匈牙利算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一.介绍

匈牙利算法几乎是二分图匹配的核心算法,除了二分图多重匹配外均可使用

匈牙利算法实际上就是一种网络流的思想,其核心就是寻找增广路

二.流程

板题:hdu2063 链接:https://acm.hdu.edu.cn/showproblem.php?pid=2063

给定的关系,先进行匹配,如果遇到没法匹配的情况,那么给之前匹配的进行重新匹配,直接找到一种可行的匹配。

例如:

如果女1和男1,男2,有关系,女2和男2,男3有关系,女3和男1,男2有关系,女4和男3有关系。

先让,女1和男1匹配。

再让女2和男2匹配。

到女3,她和男1有关系,但已经被女1抢走了,试着给女1重新分配一下,结果他和男2有关系,但男2被女2抢走了,继续给女2重新分配对象,
得到男3.然后回溯回去。

到女4,进行上述过程,发现无法匹配,所以她就没男的了。

结束。

三 .源代码

#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
using namespace std;
vector<ll>e[N];
bool vis[N];
ll gril[N];
bool found(ll x)
{
	for(auto it:e[x])
	{
		if(!vis[it])
		{
			vis[it]=1;
			if(!gril[it]||found(gril[it]))
			{
				gril[it]=x;
				return 1;
			}
		}
	}
	return 0;
}
void solve()
{
	int k,m,n;
	while(cin>>k&&k)
	{
		mem(gril,0);
		cin>>m>>n;
		for(int i=1;i<=m;i++)
		{
			e[i].clear();
		}
		for(int i=1;i<=k;i++)
		{
			ll u,v;
			cin>>u>>v;
			e[u].pb(v);
		}
		ll res=0;
		for(int i=1;i<=m;i++)
		{
			mem(vis,0);
			if(found(i))res++;
		}
		cout<<res<<endl;
	}
}
int main()
{
	int t;
	t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

这篇关于匈牙利算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!