这道题，是个人都看得出来，是求一个二分图的最大匹配。
但是网络流24题嘛，我们考虑一下用网络流的方法做。
一般二分图的题，转网络流做，都需要建立一个起点和汇点。然后求一个最大流，这个最大流就是二分图的最大匹配。
我用的是Edmonds-Karp算法bfs版本
代码
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<queue> using namespace std; int n,m,s,t,tot,maxflow; const int inf = 1<<29,N=2010,M=20010; int head[N],ver[M],edge[M],Next[M],v[N],incf[N],pre[N]; //邻接表最后一个点（表头），下一个节点，流量，邻接表，数组，增广路上各边最小剩余容量，路径记录 void add(int x,int y,int z){ ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;//正向边 ver[++tot]=x,edge[tot]=0,Next[tot]=head[y],head[y]=tot;//反向边 } bool bfs(){ memset(v,0,sizeof(v)); queue<int>q; q.push(s); v[s]=1; incf[s]=inf;//增广路上各边最小剩余容量 while(q.size()){ int x=q.front(); q.pop(); for (int i=head[x];i!=-1;i=Next[i])//开始广度遍历 if (edge[i]){//流量不为0 int y=ver[i]; if(v[y])continue;//这条边在当前的BFS里面已经走过了 incf[y]=min(incf[x],edge[i]); pre[y]=i;//记录前驱，方便把方案保存下来 q.push(y),v[y]=1; if (y==t)return 1;//成功 } } return 0;//失败 } void update(){ int x=t; while(x!=s){ int i=pre[x]; edge[i]-=incf[t];//更新流量 edge[i^1]+=incf[t];//更新反向流量 x=ver[i^1]; } maxflow+=incf[t]; } int main(){ int tmp1,tmp2; while(~scanf("%d%d",&m,&n)){ memset(head,-1,sizeof(head)); s=0,t=n+1,tot=1,maxflow=0; while(1){ scanf("%d%d",&tmp1,&tmp2); if (tmp1==-1 && tmp2==-1) break; add(tmp1,tmp2,0x3f3f3f3f); } for (int i=1;i<=m;i++){ add(s,i,1); } for (int i=m+1;i<=n;i++){ add(i,t,1); } while(bfs()) update(); printf("%d\n",maxflow); for (int i=2;i<=tot;i+=2){ if((ver[i^1]!=s && ver[i]!=t)&&(ver[i]!=s && ver[i^1]!=t))//不能是直接指向起点和汇点的点 if (edge[i^1]!=0) printf("%d %d\n",ver[i^1],ver[i]); } } return 0; }
留坑匈牙利算法