算法1
(暴力枚举) $O(n^2)$
这个代码没有AC哦
16个数据过了4个
C++ 代码
//直接在做的时候不是很看得懂题目;求二分图的最大匹配个数:一条边左右各占一个点.
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 510;
using namespace std;
//设置一个二维数组将他们意义对应,是的话,就标记1,不是的话,就标记0;!!!
int n1,n2,m,a,b;
int g[N][N];//代表有没有边
bool st[3][N];//代表双向点构造的边有没有!!!,st[1][]代表集合一已经遍历过的点,同理.之后标记true,然后(!st[][]).
int max_match()
{
int res = 0;
bool flag = true;
for(int i = 1 ; i <= n1 ; i ++)
{
for(int j = 1 ; j <= n2 ; j++)
{
if( g[i][j] && !st[1][i] && !st[2][j]) //如果这个点被访问过的话!!!,那么它的双指向都需要标记
{
st[2][j] = st[1][i] = true;
res ++;
}
}
}
return res;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&m);
while(m--)
{
scanf("%d%d",&a,&b);
g[a][b] = 1;//某种意义上讲这是一种有向图
}
int t = max_match();
cout << t << endl;
}
C++ AC的代码
//这里用的是模拟链表,不是二维数组.
#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 510,M = 100010;
using namespace std;
int n1,n2,m,a,b;
int h[N],e[M],ne[M],idx;
int match[N];//看有无对象
bool st[N];//不要重复搜一个点
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
bool find(int x)
{
for(int i = h[x] ; i != -1 ; i = ne[i])//枚举所有看上的妹子
{
int j = e[i];
if(!st[j])//没有重
{
st[j] = true;
if(match[j] == 0 || find(match[j]))//当妹子没有匹配对象并且它匹配的对象可以找下家的时候
{
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof h);
while(m--)
{
scanf("%d%d",&a,&b);
add(a,b);
}
int res = 0;
for(int i = 1; i <= n1 ; i++)//从一头找即可,因为另一头是定的!!!
{
memset(st,false , sizeof st);
if(find(i)) res++;//如果找到对象了
}
printf("%d\n",res);
return 0;
}