本文共 1283 字，大约阅读时间需要 4 分钟。

题目大意： 有 $n$ 个男生和 $m$ 个女生，给出若干组关系，每组形如 $x,y$，表示男生 $x$ 可以和女生 $y$ 配对，问最多能成全几对并输出一种方案。

题解

二分图最大匹配，由于数据范围很小，匈牙利算法和网络流都可以的。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 10010int n,m,S,T,E=0;struct edge{
   int x,y,z,next;};edge e[maxn<<1];int first[maxn],len=1;void buildroad(int x,int y,int z){
   	e[++len]=(edge){
   x,y,z,first[x]};	first[x]=len;}int h[maxn],q[maxn],st,ed;bool bfs(){
   	memset(h,0,sizeof(h));	st=ed=1;q[st]=S;h[S]=1;	while(st<=ed)	{
   		int x=q[st++];		for(int i=first[x];i;i=e[i].next)		if(!h[e[i].y]&&e[i].z)h[q[++ed]=e[i].y]=h[x]+1;	}	return h[T];}int dfs(int x,int flow){
   	if(x==T)return flow;	int tt=0,p;	for(int i=first[x];i;i=e[i].next)	{
   		int y=e[i].y;		if(h[y]==h[x]+1&&e[i].z)		{
   			p=dfs(y,min(e[i].z,flow-tt));tt+=p;			e[i].z-=p;e[i^1].z+=p;			if(tt==flow)break;		}	}	if(!tt)h[x]=0;	return tt;}int main(){
   	scanf("%d %d",&n,&m);S=n+m+1,T=S+1;	int x,y;	while(scanf("%d %d",&x,&y),x!=-1)	buildroad(x,y,1),buildroad(y,x,0),E++;	for(int i=1;i<=n;i++)buildroad(S,i,1),buildroad(i,S,0);	for(int i=1;i<=m;i++)buildroad(i+n,T,1),buildroad(T,i+n,0);	int ans=0;	while(bfs())ans+=dfs(S,999999999);	printf("%d\n",ans);	for(int i=2;i<=2*E;i+=2)	if(!e[i].z)printf("%d %d\n",e[i].x,e[i].y);}
     
    
   

转载地址：http://ecnib.baihongyu.com/