图论训练之十四

复习一下网络流二分图

https://www.luogu.org/problem/P3386

分析：没什么好分析的.......

因为没学过匈牙利算法，所以就打一个网络流

建一个超级源点和一个超级汇点

此时最大匹配=最大流

code by wzxbeliever：

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ri register int
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=2005;
const int maxm=1002005;
const int inf=0x7fffffff;
struct node{
	int to,next,w;
}edg[maxm<<1];
int cnt,n,m,S,T,x,y,k;
int dp[maxn],head[maxn];
queue<int>Q;
il void add(int u,int v,int w){
	cnt++;
	edg[cnt].next=head[u];
	edg[cnt].to=v;
	edg[cnt].w=w;
	head[u]=cnt;
}
il bool bfs(){
	while(!Q.empty())Q.pop();
	memset(dp,0,sizeof(dp));
	dp[S]=1;Q.push(S);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(ri i=head[u];i;i=edg[i].next){
			int to=edg[i].to;
			if(!dp[to]&&edg[i].w>0)dp[to]=dp[u]+1,Q.push(to);
		}
	}
	return dp[T];
}
il int dfs(int u,int flow){
	if(u==T)return flow;
	int re=flow,k;
	for(ri i=head[u];i;i=edg[i].next){
		int to=edg[i].to;
		if(edg[i].w>0&&dp[to]==dp[u]+1&&re>0){
			k=dfs(to,min(edg[i].w,re));
			if(k>0)
			edg[i].w-=k,edg[i^1].w+=k,re-=k;
		}
	}
	return flow-re;
}
il int dinic(){
	int ans=0;
	while(bfs())ans+=dfs(S,inf);
	return ans;
}
int main(){
	scanf("%d%d%d",&x,&y,&k);
	n=x+y+2;
	for(ri i=1,u,v;i<=k;i++){
		scanf("%d%d",&u,&v);
		if(u<=x&&v<=y)
		add(u+1,v+x+1,1),add(v+x+1,u+1,0);
	}
	for(ri i=1;i<=x;i++)add(1,i+1,1),add(i+1,1,0);
	for(ri i=1;i<=y;i++)add(i+x+1,n,1),add(n,i+x+1,0);
	S=1,T=n;
	printf("%d
",dinic()); 
	return 0;
}