网站建设去哪可接单,开发国外优惠卷网站如何做,全网品牌推广企业,设计公司网站什么重要例题#xff1a;
题目#xff1a;活动 - AcWing 二分图的最大匹配 给定一个二分图#xff0c;其中左半部包含 n1 个点#xff08;编号 1∼n1#xff09;#xff0c;右半部包含 n2 个点#xff08;编号 1∼n2#xff09;#xff0c;二分图共包含 m条边。 数据保证任意…例题
题目活动 - AcWing 二分图的最大匹配 给定一个二分图其中左半部包含 n1 个点编号 1∼n1右半部包含 n2 个点编号 1∼n2二分图共包含 m条边。 数据保证任意一条边的两个端点都不可能在同一部分中。 请你求出二分图的最大匹配数。 二分图的匹配给定一个二分图 G在 G 的一个子图 M 中M 的边集 {E} 中的任意两条边都不依附于同一个顶点则称 M是一个匹配。 二分图的最大匹配所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配其边数即为最大匹配数。 输入格式
第一行包含三个整数 n1、 n2 和 m。
接下来 m 行每行包含两个整数 u 和 v表示左半部点集中的点 u 和右半部点集中的点 v之间存在一条边。
输出格式
输出一个整数表示二分图的最大匹配数。
数据范围
1≤n1,n2≤500,1≤u≤n1,1≤v≤n2,1≤m≤105
输入样例
2 2 4
1 1
1 2
2 1
2 2输出样例
2代码
#includeiostream
#includecstdio
#includestring
#includecstring
#includestring.h
#includealgorithm
#includecmath
#includevector
#includequeue
#includestack
#includemap
using namespace std;
typedef pairint,int PII;
const int N 1e5 10;
int n1,n2,m;
int v,u;
int e[N],ne[N],h[N],idx;
int st[N],match[N];
void add(int a,int b){e[idx] b,ne[idx] h[a],h[a] idx ;
}
bool find(int x){for(int i h[x];i ! -1;i ne[i]){int b e[i];if(!st[b]){st[b] 1;// 当前尝试点没有被匹配或者和当前尝试点匹配的那个点可以换另一个匹配if(match[b] 0 || find(match[b])){// 和当前尝试点匹配在一起match[b] x;return true;}}}return false;
}
int main(){memset(h,-1,sizeof h);scanf(%d %d %d,n1,n2,m);for(int i 0;i m;i ){cin v u;add(v,u);}int res 0;//为各个点找匹配for(int i 1;i n1;i ){memset(st,0,sizeof st);//找到匹配if(find(i))res ;}printf(%d,res);return 0;
}
