题目大意:二分图匹配裸题。
题解:用网络流进行处理。
找配对方案的时候,采用遍历二分图左边的每个节点,找到不与源点相连,且正向边权值为 0,反向边权值为 1 的边,输出即可。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
const int maxm=1e4+10;
const int inf=1<<30;
int n,m,s,t,d[maxn],maxflow;
struct node{int nxt,to,w;}e[maxm<<1];
int tot=1,head[maxn];
inline void add_edge(int from,int to,int w){
e[++tot]=node{head[from],to,w},head[from]=tot;
e[++tot]=node{head[to],from,0},head[to]=tot;
}
bool bfs(){
queue<int> q;
memset(d,0,sizeof(d));
d[s]=1,q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(w&&!d[v]){
d[v]=d[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dinic(int u,int flow){
if(u==t)return flow;
int rest=flow;
for(int i=head[u];i&&rest;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(w&&d[v]==d[u]+1){
int k=dinic(v,min(rest,w));
if(!k)d[v]=0;
e[i].w-=k,e[i^1].w+=k,rest-=k;
}
}
return flow-rest;
}
void read_and_parse(){
int x,y;
scanf("%d%d",&m,&n);
while(scanf("%d%d",&x,&y)&&x!=-1)add_edge(x,y,1);
for(int i=1;i<=m;i++)add_edge(0,i,1);
for(int i=m+1;i<=n;i++)add_edge(i,n+1,1);
s=0,t=n+1;
}
void solve(){
while(bfs())while(int now=dinic(s,inf))maxflow+=now;
if(maxflow==0)return (void)puts("No Solution!");
printf("%d\n",maxflow);
for(int u=1;u<=m;u++)
for(int i=head[u];i;i=e[i].nxt)
if(e[i].to!=s&&e[i].w==0&&e[i^1].w==1)
printf("%d %d\n",u,e[i].to);
}
int main(){
read_and_parse();
solve();
return 0;
}