P3386 【模板】二分图匹配

 

题目描述

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

输入输出格式

输入格式：

 

第一行，n,m,e

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

 

输出格式：

 

共一行，二分图最大匹配

 

输入输出样例

输入样例#1： 复制

1 1 1 1 1

输出样例#1： 复制

1

二分最大匹配模板题，我只是想贴个模板代码而已

下面是优化了uesd数组，用lk替代了memset（uesd），

#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int k,m,n,lk,used[N],part[N]; int ma[N][N]; bool find(int x) {for(int i=1;i<=m;i++){if(ma[x][i]&&used[i]!=lk){used[i]=lk;if(part[i]==0||find(part[i])){part[i]=x;return 1;}}}return 0; } int match() {int sum=0;for(int i=1;i<=n;i++){//memset(used,0,sizeof(used));//优化此处 lk++;if(find(i)) sum++;}return sum; } int main() {cin>>n>>m>>k;for(int i=1;i<=k;i++){int u,v;scanf("%d%d",&u,&v);ma[u][v]=1;//ma[v][u]=1;//注意这个不需要 }printf("%d\n",match());return 0; }

 

总结

以上是生活随笔为你收集整理的P3386 【模板】二分图匹配（匈牙利模板）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。