建一个超级源点s，超级汇点t。
s连向二分图中左部图的每个节点，边权为1.
二分图中右部图的每个节点连向t，边权为1.
左右部图连边的边权为1。
注意上述建边不要忘了建反向权值为0的边，方便撤销影响。
然后跑dinic即可。 dinic跑二分图的复杂度为m*sqrt(n)
最后要打印匹配。
考虑dinic的过程，最后的网络，每条边的反向边有流量(或者正向边无流量)，就说明这条边被选中了，输出即可。
最后说一下：其实网络流就是找s-t的路径数，每条边的边权就可以看成x -> y 的路径数。
dfs+可撤销找路径数，其实就是dinic。。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 5000+7; const int N = 200+7; struct Dinic{ //N个点，M条边 //add建双向边，然后D.gao ,最后输出maxflow #define inf 0x3f3f3f3f ll maxflow;int s,t,n; int v[N],pre[N],d[N],now[N]; ll incf[N]; int head[N],cnt=1; struct EDGE{int to,nxt;ll w;}ee[M*2]; inline void AD(int x,int y,ll w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} inline void add(int x,int y,ll w){AD(x,y,w);AD(y,x,0);} inline bool bfs()//在残量网络上构造分层图 { memset(d,0,sizeof(d)); queue<int>q; q.push(s);d[s]=1; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];i;i=ee[i].nxt) { int y=ee[i].to;ll w=ee[i].w; if(w&&!d[y]) { q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } } return false; } inline int dinic(int x,int flow) { if(x==t)return flow; ll rest = flow,k; for(int i=now[x];i&&rest;i=ee[i].nxt) { int y=ee[i].to;ll w= ee[i].w; now[x]=i; if(w&&d[y]==d[x]+1) { k=dinic(y,min(rest,w)); if(!k)d[y]=0;//剪枝，去掉增广完毕的点 ee[i].w-=k; ee[i^1].w+=k; rest-=k; } } return flow - rest; } inline void gao() { int flow=0; while(bfs()) { for(int i=0;i<=n;i++)now[i]=head[i]; while(flow=dinic(s,inf))maxflow+=flow; } } inline void init(int nn,int S,int T) { cnt=1;maxflow=0; for(int i=0;i<=n;i++)head[i]=0; s=S,t=T,n=nn; } }D; struct node{ int x,y,id; }p[M]; int main() { int n,m,s,t; cin>>n>>m;//左部图节点个数n，右部图节点个数m int N=n+m+2; s=n+m+1,t=n+m+2; D.init(N,s,t); int sz=0; while(1) { int x,y; scanf("%d%d%",&x,&y); if(x==-1)break; D.add(x,y,1); p[++sz]=node{x,y,D.cnt};//如果某条边的反向边流量不为零，则说明这条边跑dinic时被选中了 } for(int i=1;i<=n;i++)D.add(s,i,1); for(int i=n+1;i<=n+m;i++)D.add(i,t,1); int flow=0; D.gao(); cout<<D.maxflow<<endl; for(int i=1;i<=sz;i++){ if(D.ee[p[i].id].w){ cout<<p[i].x<<" "<<p[i].y<<endl; } } return 0; }
