洛谷P3386——二分图匹配

2021年09月15日 阅读数:3
这篇文章主要向大家介绍洛谷P3386——二分图匹配,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目:https://www.luogu.org/problemnew/show/P3386ios

二分图匹配模板,注意左部点只dfs未匹配点。ide

代码以下:spa

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,e,a[1005],b[2005],ct,head[1005],pre[2005],ans;
bool vis[1005];
struct N{
	int to,next;
}edge[300005];
void add(int x,int y)
{
	ct++;
	edge[ct].to=y;
	edge[ct].next=head[x];
	head[x]=ct;
}
bool dfs(int x)
{
	for(int i=head[x];i;i=edge[i].next)
	{
		int u=edge[i].to;
		if(vis[u])continue;
		vis[u]=1;
		if(!pre[u]||dfs(pre[u]))
		{
			pre[u]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d",&n,&m,&e);
	for(int i=1;i<=e;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(y>m||x>n)continue;
		add(x,y);
	}
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof vis);
		if(dfs(i)),ans++;
	}
	printf("%d",ans);
	return 0;
}