首页 > 代码库 > 洛谷—— P3386 【模板】二分图匹配

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

2024-09-23 23:59:35   215人阅读

https://www.luogu.org/problem/show?pid=3386

题目背景

二分图

题目描述

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

输入输出格式

输入格式：

 

第一行，n,m,e

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

 

输出格式：

 

共一行，二分图最大匹配

 

输入输出样例

输入样例#1：
1 1 11 1
输出样例#1：
1

说明

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

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

算法：二分图匹配

 

匈牙利算法：技术分享

 

 1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4  5 using namespace std; 6  7 const int N(1010); 8 int n,m,e,u,v,ans; 9 int map[N][N];10 11 int match[N],vis[N];12 13 bool DFS(int now)14 {15     for(int i=1;i<=m;i++)16         if(map[now][i]&&!vis[i])17         {    //有好感 正单身 18             vis[i]=1;    //尝试一下 19             if(!match[i]||DFS(match[i]))20             {    //对方正单身， 对方开始尝试 21                 match[i]=now;    //尝试成功 22                 return true;23             }24         }25     return false;26 }27 28 int main()29 {    30     scanf("%d%d%d",&n,&m,&e);31     for(;e;e--)32     {33         scanf("%d%d",&u,&v);34         if(u>n||v>m) continue; 35         map[u][v]=1;36     }37     for(int i=1;i<=n;i++)38     {39         memset(vis,0,sizeof(vis));40         if(DFS(i)) ans++;    //配对成功 41     }42     printf("%d\n",ans);43     return 0;44 }

 

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


联系
我们