题解：P10937 車的放置

原题链接

• 洛谷 P10937 車的放置

题意简述

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

解题思路

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

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

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

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

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

参考代码

#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])
		{
			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++)
	{
		memset(vis,0,sizeof vis);
		ans+=match(i);
	}
	cout<<ans<<'\n';
	return 0;
}