跳到主要内容

二分图

参考资料​

匈牙利算法​

bool match(int u)
{
	for(auto v:G[u])
	{
		if(vis[v])continue;
		vis[v]=1;
		if(!a[v]||match(a[v]))
		{
			a[v]=u;
			return 1;
		}
	}
	return 0;
}

例题​

洛谷 P3386 【模板】二分图最大匹配​

洛谷 P3386 【模板】二分图最大匹配

给定一个二分图，其左部点的个数为 nn，右部点的个数为 mm，边数为 ee，求其最大匹配的边数。

左部点从 11 至 nn 编号，右部点从 11 至 mm 编号。

代码（2）
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int N=1005;
struct Edge
{
	int v,w,id;
};
vector<Edge> G[N];
int pre[N],fa[N],dis[N];
bool vis[N];
int s,t;
void add(int u,int v)
{
	int uid=G[u].size(),vid=G[v].size();
	G[u].push_back({v,1,vid});
	G[v].push_back({u,0,uid});
}
bool bfs()
{
	memset(vis,0,sizeof vis);
	queue<int> q;
	q.push(s);
	vis[s]=1;
	dis[s]=inf;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<G[u].size();i++)
		{
			auto [v,w,id]=G[u][i];
			if(!w||vis[v])continue;
			dis[v]=min(dis[u],w);
			pre[v]=i;
			fa[v]=u;
			q.push(v);
			vis[v]=1;
			if(v==t)return 1;
		}
	}
	return 0;
}
ll ans=0;
void update()
{
	for(int i=t;i!=s;i=fa[i])
	{
		G[fa[i]][pre[i]].w-=dis[t];
		G[i][G[fa[i]][pre[i]].id].w+=dis[t];
	}
	ans+=dis[t];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,e;
	cin>>n>>m>>e;
	s=n+m+1;t=n+m+2;
	for(int i=1;i<=n;i++)add(s,i);
	for(int i=n+1;i<=n+m;i++)add(i,t);
	while(e--)
	{
		int u,v;
		cin>>u>>v;
		v+=n;
		add(u,v);
	}
	while(bfs())update();
	cout<<ans<<'\n';
	return 0;
}

洛谷 P10937 車的放置​

洛谷 P10937 車的放置

给定一个 NN 行 MM 列的棋盘，已知某些格子禁止放置。

问棋盘上最多能放多少个不能相互攻击的車。

車放在格子里，攻击范围与中国象棋的“車”一致。

题解

题意简述​

在一个 n×mn\times m 的矩阵中，给定 tt 个不可选的位置。要求在满足每行和每列最多选择一个点的前提下，求最多可以选取多少个点。

解题思路​

可以将问题转化为二分图匹配。

将矩阵的每一行和每一列分别看作二分图中的一组点。

如果某个位置可以选取，就在其所在行和列对应的节点之间连一条边。

这样每行只能匹配一个列节点，确保每行和每列最多选一个点。

所以问题的答案即为该二分图的最大匹配数。

参考代码​

#include <bits/stdc++.h>
using namespace std;

const int N=205;
vector<int> G[N<<1];
int a[N<<1];
bool b[N][N],vis[N<<1];
bool match(int u)
{
	for(auto v:G[u])
	{
		if(vis[v])continue;
		vis[v]=1;
		if(!a[v]||match(a[v]))
		{
			a[v]=u;
			return 1;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,t;
	cin>>n>>m>>t;
	while(t--)
	{
		int u,v;
		cin>>u>>v;
		b[u][v]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!b[i][j])G[i].push_back(j+n);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int i=1;i<=n+m;i++)vis[i]=0;
		if(match(i))ans++;
	}
	cout<<ans<<'\n';
	return 0;
}