UPC-5063-二分图最大匹配

好吧二分图的最小点覆盖=最大匹配

这道题也就变成模板题了。。。

写一个提醒,在写二分图时,尽量清零操作清空为-1,比如这个题,匹配数组girl[]如果清空为0,代表每个点都与0点连接,但是实际上是并没有

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool line[][];
bool used[];
int girl[];
int m,n,e;
bool findd(int x){
for (int i=;i<=n-;i++){//右边匹配情况
if (line[x][i]== && used[i]==false)
{
used[i]=;
if (girl[i]==- || findd(girl[i]))
{
girl[i]=x;
return ;
}
}
}
return ;
}
int main(){
int a;
while(~scanf("%d",&m)){
if (m==)break;
memset(line,,sizeof(line));
memset(used,,sizeof(used));
memset(girl,-,sizeof(girl));
scanf("%d%d",&n,&e);
int sum=;
int x,y;
while(e--){
scanf("%d%d",&x,&y);
line[x][y]=;
}
for (int i=;i<=m-;i++){
memset(used,,sizeof(used));
if (findd(i))sum++;
}
printf("%d\n",sum);
}
return ;
}
上一篇:Behave step matcher


下一篇:MySQL存储引擎--MyISAM与InnoDB区别