目录
显示
题目链接
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; }