[洛谷 2756]飞行员配对方案问题

题目链接

https://www.luogu.org/problem/P2756

题解

经典的二分图最大匹配问题。

当然可以跑一次最大流来解决，但这里我们来介绍一下经典的匈牙利算法。

过程其实不算难，主要就是通过 dfs 找增广路。

何为增广路？就是通过连接两个未匹配节点，使得匹配数量 +1 的一条路径。

匈牙利算法的过程是这样的：

对于每一个点，dfs 寻找增广路。

我们找到的每一个点可能有两种情况：如果找到一个还没匹配的点，就直接匹配上。

但假如该点已经匹配到了其他点，那我们就为这个点重新寻找一个匹配点。如果找到了，就重新安排匹配。（显然，这么做会让总匹配数 +1，因为必然会有一对未匹配点会变为匹配点）

#include <stdio.h>
#include <string.h>
struct edge
{
 int v,next;
}e[10005];
int head[205],cnt,vis[205],march[205];
bool find(int x)
{
 for(int i=head[x];i;i=e[i].next)
  if(!vis[e[i].v])
  {
   vis[e[i].v]=1;
   if(!march[e[i].v]||find(march[e[i].v]))
   {
    march[e[i].v]=x;
    return true;
   }
  }
 return false;
}
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
int main()
{
 int m,n,u,v,ans=0;
 scanf("%d%d",&m,&n);
 while((~scanf("%d%d",&u,&v))&&(~u)&&(~v))
  addedge(u,v);
 for(int i=1;i<=n;i++)
 {
  memset(vis,0,sizeof(vis));
  if(find(i))ans++;
 }
 printf("%d\n",ans);
 for(int i=m+1;i<=n;i++)
  if(march[i])printf("%d %d\n",march[i],i);
 return 0;
}