喜报：我们给这题加了个hack，匈牙利过不去了。

本题解因时间复杂度不符，已被优化$hack$掉2分了.......................................

属于比较板子的题，就是二分最大匹配加一点改变和优化即可

纯模板

看到题目，没有学过二分图最大匹配的请看这道题：

D25：二分图最大匹配

这道题就是在输出情况数的基础上再输出匹配方案

所以首先想到的就是在模板的基础上输出储存方案的数组，但要注意一个细节，模板的匹配方案是记录在右部的，所以输出时遍历的是右部，而且编号从$0$开始，记得数组初始化时要赋值$-1$

然后就可以得到一个90分快要AC的TLE代码了......

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int>G[N];
int match[N],v[N],tsp,Ln,Rn,m,ans=0;
bool dfs(int x)
{
	for(int y:G[x])if(v[y]!=tsp)
	{
		v[y]=tsp;
		if(match[y]<0||dfs(match[y]))
		{
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d",&Ln,&Rn,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].emplace_back(y);
	}
	memset(match,-1,sizeof match);
	memset(v,0,sizeof v);
	for(int i=0;i<Ln;i++)
	{
		tsp=i+1;
		if(dfs(i))ans++;
	}
	printf("%d\n",ans);
	for(int i=0;i<Rn;i++)if(match[i]>=0)printf("%d %d\n",match[i],i);
	return 0;
}

优化

既然板子都90分了，再优化亿点点就可以AC了，所以在板子中能优化哪里呢？

那就是在遍历匹配时下功夫了，我们可以从能够匹配另一部分的数最少的数开始匹配 (怎么这么绕口)，可以减少亿点增广匹配次数......

然后实现就可以AC了 但快4.5s的运行时间让我以为过不了

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int>G[N];
int match[N],v[N],tsp,Ln,Rn,m;
bool cmp(int a,int b){return G[a].size()<G[b].size();}
bool dfs(int x)
{
	for(int y:G[x])if(v[y]!=tsp)
	{
		v[y]=tsp;
		if(match[y]<0||dfs(match[y]))
		{
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d",&Ln,&Rn,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
	}
	vector<int>l;
	for(int i=0;i<Ln;i++)l.push_back(i);
	sort(l.begin(),l.end(),cmp);
	memset(match,-1,sizeof match);
	int ans=0;
	for(int x:l)
	{
		tsp++;
		if(dfs(x))ans++;
	}
	printf("%d\n",ans);
	for(int i=0;i<Rn;i++)if(match[i]>=0)printf("%d %d\n",match[i],i);
	return 0;
}

嘲讽一小下，$kevin$的代码还是太专业了，但怎么是最差解呢......

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define int long long
struct node{int to,v,nxt;}e[N];int head[N],len;
void add(int x,int y,int c)
{
	e[++len]={y,c,head[x]};head[x]=len;
	e[++len]={x,0,head[y]};head[y]=len;	
}
int cur[N],d[N],st,ed;
bool find()
{
	memset(d,0,sizeof(d));d[st]=1;
	deque<int>q;q.push_back(st);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(d[y]==0&&e[i].v)
			{
				d[y]=d[x]+1;
				q.push_back(y);
				if(y==ed)return 1;
			}
		}
	}
	return 0;
}
int flow(int x,int s)
{
	if(x==ed)return s;
	int ans=0;
	for(int i=cur[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		cur[x]=i;
		if(d[y]==d[x]+1&&e[i].v)
		{
			int sum=flow(y,min(e[i].v,s));
			e[i].v-=sum;
			e[i^1].v+=sum;
			ans+=sum;
			s-=sum;
			if(s==0)break;
		}
	}
	if(ans==0)d[x]=0;
	return ans;
}
int dinic()
{
	int ans=0;
	while(find())
	{
		memcpy(cur,head,sizeof(cur));
		ans+=flow(st,1e18);
	}
	return ans;
}
signed main()
{
	int n1,n2,m;cin>>n1>>n2>>m;len=1;
	st=0,ed=n1+n2+1;
	for(int i=1;i<=n1;i++)add(st,i,1);
	for(int i=1;i<=n2;i++)add(i+n1,ed,1);
	for(int i=1;i<=m;i++)
	{
		int x,y;cin>>x>>y;
		add(x+1,y+n1+1,1);
	}
	int ans=dinic();
	cout<<ans<<'\n';
	for(int i=1;i<=n1;i++)
		for(int j=head[i];j;j=e[j].nxt)
			if(e[j].v==0&&e[j].to>n1)
				cout<<i-1<<' '<<e[j].to-n1-1<<'\n';
	return 0;
}