P3386 【模板】二分图匹配

题目背景

二分图

题目描述

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

输入输出格式

输入格式：

第一行，n,m,e

第二至e+1行，每行两个正整数u,v，表示u,v有一条连边

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1：

1 1 1

1 1

输出样例#1：

说明

n,m≤1000 ， 1≤u≤n ， 1≤v≤m

因为数据有坑，可能会遇到 v>mv>mv>m 的情况。请把 v>mv>mv>m 的数据自觉过滤掉。

算法：二分图匹配

Solution：

二分图最大匹配的模板，直接套上匈牙利算法，至于实现可以去看博客（因为别人写的太好了，感觉自己写还不如别人清楚，所以就不写二分图匹配的详解了）。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 const int N=;

 inline int gi()

 {

     char x=getchar();int a=,f=;

     while(x<''||x>''){if(x=='-')f=-;x=getchar();}

     while(x>=''&&x<=''){a=a*+x-'';x=getchar();}

     return a*f;

 }

 int n,m,s,u,v;

 struct edge

 {

     int v,ne;

 }e[N*N<<];

 int h[N],cnt;

 inline void ins(int u,int v){

     e[++cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;

 }

 int le[N];

 bool vis[N];

 bool find(int u){

     for(int i=h[u];i;i=e[i].ne){

         int v=e[i].v;

         if(!vis[v]){

             vis[v]=;

             if(!le[v]||find(le[v])){

                 le[v]=u;

                 return ;

             }

         }

     }

     return ;

 }

 int ans;

 int main(){

     n=gi();m=gi();int t=gi();

     for(int i=;i<=t;i++){u=gi();v=gi();if(v>m||u>n)continue;ins(u,v);}

     for(int i=;i<=m;i++){

         memset(vis,,sizeof(vis));

         if(find(i)) ans++;

     }

     printf("%d\n",ans);

     return ;

 }

秒客网