二分匹配（匈牙利算法）模板
生活随笔
收集整理的这篇文章主要介绍了
二分匹配（匈牙利算法）模板
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
#include <iostream>
#include <vector>
using namespace std;
#define MAX 1005vector< vector<int> > map;
int mark[MAX];
bool flag[MAX];
int nm,num;bool dfs(int pos) //搜pos点是否存在增广路
{int i,pre,tp;int len=map[pos].size();for(i=0;i<len;i++){tp=map[pos][i];if(!flag[tp]){flag[tp]=true;pre=mark[tp]; mark[tp]=pos;if(pre==-1 || dfs(pre)) return true; //如果没被访问过或者存在增广路，pos到该点就存在增广路mark[tp]=pre; //否则pos到该点就不存在增广路}}return false;
}int main()
{int n,m,t,i; //n是v1集合的节点数（男孩的人数）m是v2集合的节点数（女孩的人数）t是有t对之间存在边（即有关系）while (scanf("%d%d%d",&n,&m,&t),n){num=0;nm=n+m;map.clear();map.resize(nm+10);memset(mark,-1,sizeof(mark));int x,y;while (t--){scanf("%d%d",&x,&y);y+=n;map[x].push_back(y);}for (i=1;i<=n;i++){memset(flag,0,sizeof(flag));if(dfs(i)) num++;}printf("%d/n",num);}return 0;
}
总结
以上是生活随笔为你收集整理的二分匹配（匈牙利算法）模板的全部内容，希望文章能够帮你解决所遇到的问题。
