洛谷 P3386 【模板】二分图匹配

时间：2022-03-30 20:04:21

题目背景

二分图

题目描述

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

输入输出格式

输入格式：

第一行，n,m,e

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

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1： 
1 1 1

1 1
输出样例#1： 
1

说明

n,m<=1000，1<=u<=n，1<=v<=m

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

算法：二分图匹配

++++++++++++++++++++++++++++++++++++++++++++++++++++

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstdlib>

 #include<iomanip>

 #include<cassert>

 #include<climits>

 #include<vector>

 #include<list>

 #include<map>

 #define maxn 1000001

 #define F(i,j,k) for(int i=j;i<=k;i++)

 #define M(a,b) memset(a,b,sizeof(a))

 #define FF(i,j,k) for(int i=j;i>=k;i--)

 #define inf 0x7fffffff

 #define maxm 2016

 #define mod 1000000007

 //#define LOCAL

 using namespace std;

 int read(){

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

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

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

     return x*f;

 }

 int n1,n2,m;

 int mp[maxm][maxm];

 int vis[maxn],link[maxn];

 inline bool find(int u)

 {

     F(i,,n2){

         if(mp[u][i]&&!vis[i]){

             vis[i]=;

             if(link[i]==||find(link[i])){

                 link[i]=u;

                 return true;

             }

         }

     }

     return false;

 }

 int ans=;

 int main()

 {

     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;

     #ifdef LOCAL

     freopen("data.in","r",stdin);

     freopen("data.out","w",stdout);

     #endif

     cin>>n1>>n2>>m;

     F(i,,m-){

         int x,y;cin>>x>>y;

         mp[x][y]=;

     }

     F(i,,n1){

         M(vis,false);

         if(find(i)) ans++;

     }

     cout<<ans<<endl;

     return ;

 }

相关文章