原理:
匈牙利算法:二分图最大权匹配 - OI Wiki
简单说就是挨个找,找到就退出。后面的来了就让前面的挪位置。
板子:
book指给u找位置时,有人考虑过的位置就不考虑了。
match[ i ]就是i位置对应的人。
e是关系
int book[10001];
int match[10001];
bool e[101][101];
int ans=0,n=0,m=0;
bool dfs(int u)
{
for(int i=1;i<=n;i++)
{
if(book[i]==0 && e[u][i]==true)
{
book[i]=1;
if(match[i]==0 || dfs(match[i])==true)
{
match[u]=i;
match[i]=u;
return true;
}
}
}
return false;
}
使用:
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int x=0,y=0;
scanf("%d %d",&x,&y);
e[x][y]=true;
e[y][x]=true;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
book[j]=0;
}
if(dfs(i)==true)
{
ans++;
}
}
printf("%d",ans);
return 0;
}