网络流实现二分图匹配
对于x集合的每一个点连一条从源点出发的容量为一的边,对于y集合的每一个点连一条到汇点的容量为一的边,跑最大流
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=210,MAXM=400005;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return fh*rv;
}
queue <int> q;
int head[MAXN],dep[MAXN],cur[MAXN],nume,n,m,s,t,maxflow;
struct edge{
int to,nxt,flow,cap;
}e[MAXM];
void adde(int from,int to,int cap){
e[++nume].to=to;
e[nume].nxt=head[from];
e[nume].cap=cap;
head[from]=nume;
}
bool bfs(){
memset(dep,0,sizeof(dep));
q.push(s);dep[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dep[v]&&e[i].flow<e[i].cap){
dep[v]=dep[u]+1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u,int flow){
if(u==t) return flow;
int tot=0;
for(int &i=cur[u];i&&tot<flow;i=e[i].nxt){
int v=e[i].to;
if(dep[v]==dep[u]+1&&e[i].flow<e[i].cap){
if(int t=dfs(v,min(flow-tot,e[i].cap-e[i].flow))){
e[i].flow+=t;
e[((i-1)^1)+1].flow-=t;
tot+=t;
}
}
}
return tot;
}
void dinic(){
while(bfs()){
for(int i=0;i<=n+1;i++) cur[i]=head[i];
maxflow+=dfs(s,0x3f3f3f3f);
//cout<<1<<endl;
}
}
int main(){
m=init();n=init();
s=0;t=n+1;
int u=1,v=1;
while(u!=-1&&v!=-1){
u=init();v=init();
adde(u,v,1);
adde(v,u,0);
}
int top=nume;
for(int i=1;i<=m;i++){
adde(s,i,1);
adde(i,s,0);
}
for(int i=m+1;i<=n;i++){
adde(i,t,1);
adde(t,i,0);
}
dinic();
cout<<maxflow<<endl;
for(int i=1;i<=top;i+=2){
if(e[i].flow) printf("%d %d\n",e[((i-1)^1)+1].to,e[i].to);
}
return 0;
}