代码1:
#include <stdio.h>
#include <string.h>
#define max 205
int nx,ny,e[max][max];
int cx[max],cy[max],vis[max];
int path(int u){
int v;
for(v=1;v<=ny;v++)
if(e[u][v]&&!vis[v]){
vis[v]=1;
if(cy[v]==-1||path(cy[v])){
cx[u]=v;cy[v]=u;
return 1;}}
return 0;}
int maxmatch(){
int i,res=0;
for(i=1;i<=nx;i++)
if(cx[i]==-1){
memset(vis,0,sizeof(vis));
res+=path(i);}
return res;}
int main(){
int i,p;
scanf("%d%d",&nx,&ny);
for(i=1;i<=nx;i++)
while((scanf("%d",&p)!=EOF)&&p) e[i][p]=1;
for(i=1;i<=max;i++) cx[i]=cy[i]=-1;
printf("%d",maxmatch());
return 0;}
代码2:
#include <stdio.h>
#include <string.h>
#define max 205
int nx,ny,edge[max][max];
int cx[max],cy[max],vis[max];
int path(int u){
int v;
for(v=1;v<=ny;v++)
if(edge[u][v]&&!vis[v]){
vis[v]=1;
if(cy[v]==-1||path(cy[v])){
cx[u]=v;cy[v]=u;
return 1;}}
return 0;}
int maxmatch(){
int i,res=0;
for(i=1;i<=nx;i++)
if(cx[i]==-1){
memset(vis,0,sizeof(vis));
res+=path(i);}
return res;}
int main(){
int i,p;
scanf("%d%d",&nx,&ny);
for(i=1;i<=nx;i++)
while((scanf("%d",&p)!=EOF)&&p) edge[i][p]=1;
for(i=1;i<=max;i++) cx[i]=cy[i]=-1;
printf("%d",maxmatch());
return 0;}