AcWing 863. 二分图的最大匹配 ---
原题链接
简单
作者:
呼和
,
2019-08-29 19:56:58
,
所有人可见
,
阅读 687
读懂不一样的代码,也是一种提高。
读懂题解,写一个不一样的代码,更是一种提高。
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int M = 505;
int head[M], to[N] , net[N] ,from[N] ,len = 1;
int ff[M];
int n1,n2,m;
bool vis[M];
void add(int a, int b)
{
to[len] = b;
net[len] = head[a];
head[a] = len++;
}
bool Hungarian(int x )
{
for(int i = head[x] ; i ; i = net[i])
{
if(vis[ to[i] ])
{
vis[ to[i] ] = false;
if(!ff[ to[i] ] || Hungarian(ff[to[i]]) )
{
ff[to[i]] = x;
return true;
}
// vis[ to[i] ] = true;
// 因为一个男的跟一个女的相处不来,那么肯定不会在跟他相处
}
}
return false;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&m);
for(int i = 0,x,y ; i < m ; i++)
{
scanf("%d%d",&x,&y);
add(x,y);
}
int cnt = 0;
for(int i = 1 ; i <= n1 ; i++ )
{
memset(vis,true,sizeof(vis));
if( Hungarian(i) )
cnt++;
}
printf("%d\n",cnt);
}