二分图基础初步探究

概述

二分图判定很好说就是没有奇边环即可
然后就是匈牙利算法了匈牙利算法求的是最大匹配集根据一个定理这也等于最小点覆盖集

匈牙利算法

匈牙利算法原理是通过増广路实际上也不需要这么的复杂，核心在于我前面的两个点如果已经选了我再进行匹配的时候要怎么最优化
道理在于先维护一个vis代表当前点遍历过后所有的点,这个vis巧妙而且必不可少因为如果这是保证切换寻找的时候不会出现重复的现象

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,k,l[105],r[105],mp[105][105],vis[105],ans;
int dfs(int p)
{
	for(int i=1;i<=m;i++)
	if(mp[p][i]&&!vis[i])
	{
		vis[i]=1;
		if(!r[i]||dfs(r[i]))
		{
			l[p]=i;
			r[i]=p;
			return 1;
		}
	}
	return 0;
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		if(n==0)
		break;
		memset(mp,0,sizeof(mp));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		for(int i=1;i<=k;i++)
		{
			int id,l,r;
			scanf("%d%d%d",&id,&l,&r);
			mp[l][r]=1;
		}
		ans=0;
		for(int i=1;i<=n;i++)
		{
			if(!l[i])
			{
				memset(vis,0,sizeof(vis));
				ans+=dfs(i);
			}
		}
		printf("%d\n",ans);
	}
}

最大权匹配集

匈牙利算法的升级版，应用于左右互相最大的匹配边权和最大值,匈牙利算法的重复尝试在于连接性这里要加上边权的问题
首先我们初始化左边的wl数组为边权最大的那条边的权值右边为0
接着我们每次匹配如果出现了问题，需要重复匹配按照这样的规则:
出现二夹一就要左加右减
最后把答案统计即可

代码

#include <bits/stdc++.h>
using namespace std;
int wl[305],wr[305],vl[305],vr[305],cha[305],n,a[305][305],vrr[305];
int dfs(int p)
{
	vl[p]=1;
	for(int i=1;i<=n;i++)
	{
		if(vr[i])
		continue;
		int g=wl[p]+wr[i]-a[p][i];
		if(g==0)
		{
			vr[i]=1;
			if(!vrr[i]||dfs(vrr[i]))
			{
				vrr[i]=p;
				return 1;
			}
		}
		else
		cha[i]=min(cha[i],g);
	}
	return 0;
}
int main()
{
	while(~scanf("%d",&n))
	{
		memset(wl,0,sizeof(wl));
		memset(wr,0,sizeof(wr));
		memset(vrr,0,sizeof(vrr));
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		wl[i]=max(wl[i],a[i][j]);
		for(int i=1;i<=n;i++)
		{
			memset(cha,0x7f,sizeof(cha));
			while(1)
			{
				memset(vl,0,sizeof(vl));
				memset(vr,0,sizeof(vr));
				if(dfs(i))
				break;
				int t=1<<30;
				for(int j=1;j<=n;j++)
				if(!vr[j])
				t=min(t,cha[j]);
				for(int j=1;j<=n;j++)
				{
					if(vl[j])
					wl[j]-=t;
					if(vr[j])
					wr[j]+=t;
					else
					cha[j]-=t;
				}
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		ans+=a[vrr[i]][i];
		printf("%d\n",ans);
	}
}