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

时间：2021-10-09 11:00:47

匈牙利算法模板

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int mxn=;

 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 mp[mxn][mxn];

 int n,m,et;

 int link[mxn];

 bool vis[mxn];

 bool DFS(int u){

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

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

             vis[i]=;

             if(link[i]==- || DFS(link[i])){

                 link[i]=u;

                 return ;

             }

         }

     }

     return ;

 }

 int solve(){

     int res=;

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

         memset(vis,,sizeof vis);

         if(DFS(i))res++;

     }

     return res;

 }

 int main(){

     n=read();m=read();et=read();

     int i,j;

     int u,v;

     for(i=;i<=et;i++){

         u=read();v=read();

         if(u>m || v>m)continue;

         mp[u][v]=mp[v][u]=;

     }

     memset(link,-,sizeof link);

     int ans=solve();

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

     return ;

 }

相关文章