/*二分图最大匹配,网络流最大流左边为n个点,编号从 1---n右边为m个点 编号从 n+1---n+m建立超级源点0和超级汇点n+m+1*/#include <bits/stdc++.h>using namespace std;const int maxn=510;const int maxm=5e4+10;const int inf=0x3f3f3f3f;int head[maxn<<1],cnt=0;int dis[maxn<<1];struct edge{int v,next;int c;}e[maxm<<3];void add(int u,int v,int c){e[cnt].v=v;e[cnt].c=c;e[cnt].next=head[u];head[u]=cnt++;}int n,m,E;int s=0,t;void create_graph(){memset(head,-1,sizeof(head));cnt=0;cin>>n>>m>>E;t=n+m+1;for (int i=1;i<=E;i++){int u,v;scanf(\"%d%d\",&u,&v);v+=n;add(u,v,1);add(v,u,0);}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);}}bool bfs(int s,int t){memset(dis,-1,sizeof(dis));dis[s]=0;queue<int>q;q.push(s);while(!q.empty()){int u=q.front();q.pop();for (int i=head[u];~i;i=e[i].next){int v=e[i].v,c=e[i].c;if(c>0 && dis[v]==-1){dis[v]=dis[u]+1;q.push(v);}}}return dis[t]!=-1;}int dfs(int u,int flow){if(u==t) return flow;int delta =flow;for (int i=head[u];~i;i=e[i].next){int v=e[i].v,c=e[i].c;if(c>0 && dis[v]==dis[u]+1){int d=dfs(v,min(c,delta));if(d==0) dis[v]=0;e[i].c-=d;e[i^1].c+=d;delta-=d;if(delta == 0) break;}}return flow-delta;}int dinic(int s,int t){int maxflow = 0;while(bfs(s,t)){maxflow+=dfs(s,inf);}return maxflow;}int main(){create_graph();int ans = dinic(s,t);cout<<ans<<endl;return 0;}
图论:二分图最大匹配(网络流最大流算法)
未经允许不得转载:爱站程序员基地 » 图论:二分图最大匹配(网络流最大流算法)