P3386 【模板】二分图匹配【二分图 最大匹配】

本文主要是介绍P3386 【模板】二分图匹配【二分图 最大匹配】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目背景

二分图

 

题目描述

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

 

输入格式

第一行，n,m,e

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

 

输出格式

共一行，二分图最大匹配

 

输入样例

1 1 1
1 1

输出样例

1

说明

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

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

算法：二分图匹配

问题链接：P3386 【模板】二分图匹配

解题思路：二分图模板题，使用匈牙利算法

AC的C++程序

#include<iostream>
#include<cstring>
#include<vector>using namespace std;const int N=2005;vector<int>g[N];//邻接表 
bool vis[N];//标记点集Y中的结点是否被访问 
int link[N];//记录点集Y中的结点y与点集X中的结点x相连 bool find(int x)
{ for(int i=0;i<g[x].size();i++){int y=g[x][i];if(!vis[y]){vis[y]=true;if(link[y]==-1||find(link[y])){link[y]=x;return true;}}}return false;
}int main()
{int n,m,e,u,v;scanf("%d%d%d",&n,&m,&e);while(e--){scanf("%d%d",&u,&v);if(u>n||v>m) continue;v+=n;g[u].push_back(v);g[v].push_back(u);}memset(link,-1,sizeof(link));int ans=0;for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(find(i))ans++;}printf("%d\n",ans);return 0;
}

 

这篇关于P3386 【模板】二分图匹配【二分图 最大匹配】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---