P3386 【模板】二分图匹配(匈牙利模板)

2021年09月15日 阅读数:4
这篇文章主要向大家介绍P3386 【模板】二分图匹配(匈牙利模板),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
P3386 【模板】二分图匹配

 

题目描述

给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数html

输入输出格式

输入格式:c++

 

第一行,n,m,e数组

第二至e+1行,每行两个正整数u,v,表示u,v有一条连边ide

 

输出格式:优化

 

共一行,二分图最大匹配spa

 

输入输出样例

输入样例#1: 复制code

1 1 1
1 1

输出样例#1: 复制htm

1

二分最大匹配模板题,我只是想贴个模板代码而已ci

下面是优化了uesd数组,用lk替代了memset(uesd),it

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int k,m,n,lk,used[N],part[N];
int ma[N][N];
bool find(int x)
{
	for(int i=1;i<=m;i++){
		if(ma[x][i]&&used[i]!=lk){
			used[i]=lk;
			if(part[i]==0||find(part[i])){
				part[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int match()
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		//memset(used,0,sizeof(used));//优化此处 
		lk++;
		if(find(i)) sum++;
	}
	return sum;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		ma[u][v]=1;
		//ma[v][u]=1;//注意这个不须要 
	}
	printf("%d\n",match());
	return 0;
}