建立一个超级源点和超级汇点,点与点之间的容量均为1,因为一个点只能匹配一个点,源点向所有左边的点连边,汇点向右边的点连边。最后网络的最大流即为最大匹配。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 2005
struct queue {
int q[MAXN],head,tail;
void reset() {head = 1; tail = 0;}
int front() {return q[head];}
void push(int x) {q[++tail] = x;}
void pop() {++head;}
bool empty() {return head>tail;}
}q;
struct edge {
int v,next,c;
}G[MAXN*MAXN<<1];
int d[MAXN],head[MAXN],cur[MAXN];
int N,M,E,S,T,tot = -1;
inline void add(int u,int v,int c) {
G[++tot] = (edge) {v,head[u],c}; head[u] = tot;
}
inline bool bfs() {
q.reset();
std::memset(d,0,sizeof(d));
d[S] = 1; q.push(S);
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i=head[u];i!=-1;i=G[i].next) {
if(G[i].c<=0) continue;
int v = G[i].v; if(d[v]!=0) continue;
d[v] = d[u] + 1; q.push(v);
}
}
return d[T] != 0;
}
int dfs(int u,int a) {
if(u==T) return a;
int flow = 0,temp;
for(int& i=cur[u];i!=-1;i=G[i].next) {
int v = G[i].v;
if(d[v]!=d[u]+1) continue;
if(G[i].c>0&&(temp = dfs(v,std::min(G[i].c,a)))) {
G[i].c -= temp;
G[i^1].c += temp;
flow += temp;
a -= temp;
if(a==0) return flow;
}
}
return flow;
}
inline int dinic() {
int flow = 0;
while(bfs()) {
for(int i=1;i<=N+M+2;++i) cur[i] = head[i];
flow += dfs(S,2147483647);
}
return flow;
}
int main() {
scanf("%d%d%d",&N,&M,&E);
std::memset(head,-1,sizeof(head));
int u,v;
for(int i=1;i<=E;++i) {
scanf("%d%d",&u,&v);
add(u,v+N,1); add(v+N,u,0);
}
S = N + M + 1; T = S + 1;
for(int i=1;i<=N;++i) {
add(S,i,1); add(i,S,0);
}
for(int i=N+1;i<=N+M;++i) {
add(i,T,1); add(T,i,0);
}
printf("%d",dinic());
return 0;
}