无权二分图最大匹配 HDU2063 匈牙利算法 || Hopcroft-Karp
2024-09-30 08:21:02
参考两篇比较好的博客
http://www.renfei.org/blog/bipartite-matching.html
http://blog.csdn.net/thundermrbird/article/details/52231639###;
最大匹配数为n 2*n个不同的点 n条不同的边
匈牙利算法
从未匹配的的点出发寻找 非匹配边大于匹配边的交替路(增广路)匹配边与非匹配边交换
匈牙利算法模板(DFS,邻接矩阵版) 时间复杂度O(V*E)
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;
const int maxn = ;
const int maxm = 1e4+;
const int inf = 0x3f3f3f3f;
const double epx = 1e-;
typedef long long ll;
int n,m,k;
int visit[maxn];
int match[maxn];
int a[maxn][maxn];
bool found(int x)
{
for(int i=;i<=m;i++) //从右边的集合中找能与x进行匹配的点
{
if(a[x][i]==&&visit[i]==) //x与i有联系且i没被查找过
{
visit[i]=;
if(match[i]==||found(match[i])) //第i个点还没有匹配 如果匹配了就看 与它匹配的那个点 能不能换个点完成匹配 把i空出来 如果可以i与x匹配
{
match[i]=x;
return true;
}
}
}
return false;
}
int main()
{
while(scanf("%d",&k)!=EOF&&k) //k条边
{
scanf("%d%d",&n,&m); //左右两个集合的数量
memset(a,,sizeof(a));
for(int i=;i<=k;i++)
{
int x,y;
scanf("%d %d",&x,&y);
a[x][y]=; //有联系的点标记为1
}
memset(match,,sizeof(match));
int ans=;
for(int i=;i<=n;i++) //依次对左边集合中点进行匹配
{
memset(visit,,sizeof(visit)); //清空访问标记数组
if(found(i)) //满足条件匹配数+1
ans++;
}
printf("%d\n",ans);
}
}
Hopcroft-Karp 算法
复杂度 O(sqrt(n)*E)
邻接表存图,vector 实现 ,vector 先初始化,然后加入边 , uN 为左端的顶点数,使用前赋值 (点编号 0 开始)
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n")
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl
#define ffread(a) fastIO::read(a)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = +;
const int INF = 0x3f3f3f3f;
vector<int>G[MAXN];
int uN;
int Mx[MAXN],My[MAXN];
int dx[MAXN],dy[MAXN];
int dis;
bool used[MAXN];
void init(int n)
{
uN=n;
for(int i=; i<n; i++)
G[i].clear();
}
bool SearchP()
{
queue<int>Q;
dis = INF;
memset(dx,-,sizeof(dx));
memset(dy,-,sizeof(dy));
for(int i = ; i < uN; i++)
if(Mx[i]==-)
{
Q.push(i);
dx[i] = ; }
while(!Q.empty())
{
int u = Q.front();
Q.pop();
if(dx[u] > dis)
break;
int sz = G[u].size();
for(int i = ; i < sz; i++)
{
int v = G[u][i];
if(dy[v]==-)
{
dy[v] = dx[u] + ;
if(My[v] == -)
dis = dy[v];
else
{
dx[My[v]] = dy[v] + ;
Q.push(My[v]);
}
}
}
}
return dis != INF;
}
bool DFS(int u)
{
int sz = G[u].size();
for(int i = ; i < sz; i++)
{
int v = G[u][i];
if(!used[v] && dy[v] == dx[u] + )
{
used[v] = true;
if(My[v] != - && dy[v] == dis)
continue;
if(My[v] == - || DFS(My[v]))
{
My[v] = u;
Mx[u] = v;
return true;
}
}
}
return false;
}
int MaxMatch()
{
int res = ;
memset(Mx,-,sizeof(Mx));
memset(My,-,sizeof(My));
while(SearchP())
{
memset(used,false,sizeof(used));
for(int i = ; i < uN; i++)
if(Mx[i] == - && DFS(i))
res++;
}
return res;
}
int main()
{
int n,m,k;
while(scanf("%d",&k)&&k)
{
scanf("%d%d",&m,&n);
init(m);
for(int i=; i<k; i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x-].pb(y-);
}
printf("%d\n",MaxMatch());
}
}
最新文章
- SQL SERVER 内存学习系列(二)-DMV查看内存信息
- 转载java源代码阅读方法
- hadoop浅尝 第一个hadoop程序
- Servlet中Service方法
- ThinkPHP框架一
- SpringMVC单文件上传、多文件上传、文件列表显示、文件下载(转)
- iOS类别(Category)和扩展(Extension,匿名类)
- .NET十五周年生日快乐 (3月7日发布Visual Studio 2017正式版?)
- 浅谈-Lambda
- .net表达式计算器(中缀表达式转后缀表达式,支持20多个数学函数,支持函数嵌套)
- 作业二 | Git的安装与使用
- POJ 水题(刷题)进阶
- js顺序播放列表中的音乐
- IDA Pro使用技巧
- Andriod ----配置环境变量
- Book Contents Reviews Notes Errata Articles Talks Downloads Resources Code Formatter Cover of C# in Depth Order now (3rd edition) Implementing the Singleton Pattern in C#
- 【Python】zlib压缩文件
- HttpServer发送数据到kafka
- Linux服务器部署系列之六—远程管理篇
- node.js+express+mongodb