二分图匹配
题目背景
二分图
感谢@一扶苏一 提供的hack数据
题目描述
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
输入输出格式
输入格式：
第一行，n,m,e
第二至e+1行，每行两个正整数u,v，表示u,v有一条连边
输出格式：
共一行，二分图最大匹配
输入输出样例
说明
n,m \leq 1000n,m≤1000 ， 1 \leq u \leq n1≤u≤n ， 1 \leq v \leq m1≤v≤m
因为数据有坑，可能会遇到 v>mv>m 的情况。请把 v>mv>m 的数据自觉过滤掉。
算法：二分图匹配
思路
dinic跑二分图最大流
一个源点（0）连接1到n
一个汇点（n+m+1）连接n+1到n+m
套上板子就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
#define maxn 2010001
using namespace std; int n,m,s,t;
struct node{
int v,next,cap;
}e[maxn];
int head[maxn],tot=;
int dis[maxn]; void add_node(int a,int b,int c)
{
e[++tot]=(node){b,head[a],c};
head[a]=tot;
} bool bfs()
{
memset(dis,-,sizeof(dis));
queue<int> q;
q.push(s);
dis[s]=;
while(!q.empty()) {
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].cap&&dis[v]==-)
{
dis[v]=dis[x]+;
q.push(v);
}
}
}
return dis[t]!=-;
} int dfs(int now,int f)
{
if(now==t) return f;
int rest=f;
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].cap&&rest&&dis[v]==dis[now]+)
{
int t=dfs(v,min(rest,e[i].cap));
if(!t) dis[v]=;
e[i].cap-=t;
e[i^].cap+=t;
rest-=t;
}
}
return f-rest;
} void dinic()
{
int ans=;
while(bfs())
ans+=dfs(s,inf);
printf("%d",ans);
} int main()
{
int ee;
scanf("%d%d%d",&n,&m,&ee);
int x,y;
for(int i=;i<=ee;++i) {
scanf("%d%d",&x,&y);
if(x>n||y>m) continue;
add_node(x,y+n,);
add_node(y+n,x,);
}
s=;t=n++m;
for(int i=;i<=n;++i) {
add_node(s,i,);
add_node(i,s,);
}
for(int i=;i<=m;++i) {
add_node(n+i,t,);
add_node(t,n+i,);
}
dinic();
return ;
}