HDU 2063 过山车(模板—— 二分图最大匹配问题)

时间:2023-03-08 23:34:45
HDU 2063 过山车(模板—— 二分图最大匹配问题)

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=2063

 解题思路:
二分图最大匹配模板题。
AC代码:
 #include<stdio.h>
int e[][],match[],book[],z;
int dfs(int u);
int main()
{
int t,n,m,sum,i,j,a,b;
while(scanf("%d",&t), t != )
{
scanf("%d%d",&n,&m);
z=n+m;
for(i=;i<=z;i++)
for(j=;j<=z;j++)
e[i][j]=;
for(i=;i<=t;i++)
{
scanf("%d%d",&a,&b);
e[a][n+b]=;
}
for(i=;i<=z;i++)
match[i]=;
for(sum=,i=;i<=z;i++)
{
for(j=;j<=z;j++)
book[j]=;
if(dfs(i))
sum++;
}
printf("%d\n",sum);
}
return ;
}
int dfs(int u)
{
int i;
for(i=;i<=z;i++)
{
if(!book[i] && e[u][i]==)
{
book[i]=;
if(!match[i] || dfs(match[i]))
{
match[i]=u;
match[u]=i;
return ;
}
}
}
return ;
}