了解这个算法之前 首先了解一个概念 ：增广路
增广路 ：简单的说 ，是二分图匹配中的一条边，他总是从 左边集合的一个点出发通过一条没有被匹配的边连接到右边集合，再从该点通过一条 匹配过的边连接到右边集合。
图1为 正常的二分图
图2为二分图的最大匹配
图3 为二分图最大匹配中的增广路 两条 紫色一条 黄色一条。
了解这个算法之前，还需要对一个算法进行比较： 匈牙利算法
匈牙利算法 如果用增广路来说明的话，就是从一个点出发，如果找到一个匹配 就连接这个匹配。
如果当前这个点 被匹配过的话，就去寻找一个增广路，找到左边集合中的点，看该点是否还能匹配到 右边集合的点 匹配到最后 增广路的长度为 2*n，最终无法匹配。
简单的说就是，每次判断能匹配就匹配，匹配不到就去寻找一个增广路使他继续匹配。
这样的复杂度 O(N*M)
如果数据太大，会爆TLE，所以HK算法将其复杂度优化 -> O(sqrt(n)*m)
再者：了解HK算法的本质：是对匈牙利的算法的优化，匈牙利算法一次只更新一条增广路，而HK算法，同时更新多条互不相交的最短增广路。
经证明 ：当更新到sqrt(n)的时候，最大匹配已被全部OK。复杂度证明 自行搜索。
然后开始正经的 算法讲解（一定要了解本质是对匈牙利算法的优化）：
所以根据 优化这条性质出手
第一步：他需要找到当前最短的匹配 找不到就去找最短的增广路
左边第一个点 链接到 右边第一个点 发现右边第一个点未匹配 ，那么就连起来 更新当前最短的路程
如果发现右边的点匹配过，那么就去寻找 一条增广路，用BFS实现。
比如上图中：第一次 左1连接右3，左2连接右2，左4连接右4 这是长度为1的匹配.
第二次更新：左边只有第三个点还未进行匹配，所以用第三个点更新，左3连右2，右2已经被标记过了，那么找到右2的归属者：左2，对左2进行 搜索发现可以去连接到右3，所以当前的匹配长度为3，所以继续寻找匹配，用匈牙利算法递归进行匹配即可。
这一部分的代码总结为：
/****
前期数组定义(一遍):
nR ：标记右边集合的点是否被标记
nL ：标记左边集合的点是否被标记
dR : 更新当前增广路的距离，也便于更新
dL ：同上
****/
bool judge()// 更新当前最短的增广路
{
memset(dR,-1,sizeof(dR));//初始化的意思是 ：因为多条增广路互不相交，所以一旦发生变化，另一个就不能再去标记了。
memset(dL,-1,sizeof(dL));
dis=INF;
queue<int>q;
for(int i=1;i<=n;i++) {
if(nL[i]==-1)
{
q.push(i);
dL[i]=0;
}
}
while(!q.empty())
{
int u=q.front();q.pop();
if(dL[u]>dis) break;//保证最短长度的赠广路
for(int i=1;i<=m;i++)
{
if(mp[u][i]<=t&&dR[i]==-1)//dR[i]!=-1 保证所有增广路都不相交
{
dR[i]=dL[u]+1;
if(nR[i]==-1) dis=dR[i]; //如果当前点没有被标记 ，那么可以匹配到
else//否则找到他的归属者，用归属者进入队列 ，寻找增广路
{
dL[nR[i]]=dR[i]+1;
q.push(nR[i]);
}
}
}
}
return dis!=INF;//只要能找到增广路 dis就不为INF
} 第二步：我们匹配完多条增广路之后，我们就用匈牙利的思想就去更新，这多条增广路，也是遍历左边集合中没有匹配到的点，看他们是否可以通过一条增广路匹配到，但会出现一个问题： 会增加时间，例如：
如果一个点 已经被匹配到 ，并且他是最后一个匹配的节点，那么这个节点连过去之后一定不可能成为增广路。所以不需要判断否则会耽误很多时间：
bool Find(ll x)
{
for(int i=1;i<=m;i++)
{
if(!vis[i]&&mp[x][i]<=t&&dL[x]+1==dR[i])
{
vis[i]=1;
if(nR[i]!=-1&&dR[i]==dis) continue; //特判一下
if(nR[i]==-1||Find(nR[i]))//找到就匹配，找不到就匹配他的父辈节点
{
nR[i]=x;
nL[x]=i;
return true;
}
}
}
return false;
} 第三步：进行最大匹配就可以了。结束条件是 找不到增广路：
ll MaxMatch()
{
ll cnt=0;
while(judge())
{
for(int i=1;i<=n;i++)
{
for(int k=1;k<=m;k++) vis[k]=false;
if(nL[i]==-1)
if(Find(i)) cnt++;
}
}
return cnt;
} 最后附加一个例题：
Rain on your Parade POJ的一个题：可以去搜搜
AC：
#include<bits/stdc++.h>
#define ll long long
#include <stdio.h>
#include <algorithm>
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e6+1000;
const ll INF=10000000000;
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll n,m;
ll dis;
double t;
bool vis[5000];
int nR[5000],nL[5000];
int dR[5000],dL[5000];
struct node{
double x,y;
double v;
}gest[5000],umb[5000];
double cal(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool judge()// 更新当前最短的增广路
{
memset(dR,-1,sizeof(dR));
memset(dL,-1,sizeof(dL));
dis=INF;
queue<int>q;
for(int i=1;i<=n;i++) {
if(nL[i]==-1)
{
q.push(i);
dL[i]=0;
}
}
while(!q.empty())
{
int u=q.front();q.pop();
if(dL[u]>dis) break;//保证最短长度的赠广路
for(int i=1;i<=m;i++)
{
if((cal(umb[i],gest[u])/gest[u].v)<=t&&dR[i]==-1)//dR[i]!=-1 保证所有增广路都不相交
{
dR[i]=dL[u]+1;
if(nR[i]==-1) dis=dR[i];
else
{
dL[nR[i]]=dR[i]+1;
q.push(nR[i]);
}
}
}
}
return dis!=INF;
}
bool Find(ll x)
{
for(int i=1;i<=m;i++)
{
if(!vis[i]&&(cal(umb[i],gest[x])/gest[x].v)<=t&&dL[x]+1==dR[i])
{
vis[i]=1;
if(nR[i]!=-1&&dR[i]==dis) continue;
if(nR[i]==-1||Find(nR[i]))
{
nR[i]=x;
nL[x]=i;
return true;
}
}
}
return false;
}
ll MaxMatch()
{
ll cnt=0;
while(judge())
{
for(int i=1;i<=n;i++)
{
for(int k=1;k<=m;k++) vis[k]=false;
if(nL[i]==-1)
if(Find(i)) cnt++;
}
}
return cnt;
}
void restart()
{
memset(nR,-1,sizeof(nR));
memset(nL,-1,sizeof(nL));
}
int main()
{
int T;scanf("%d",&T);
int cas=0;
bool f=false;
while(T--)
{
restart();
scanf("%lf",&t);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&gest[i].x,&gest[i].y,&gest[i].v);
scanf("%lld",&m);
for(int i=1;i<=m;i++) scanf("%lf%lf",&umb[i].x,&umb[i].y);
printf("Scenario #%d:\n%lld\n\n",++cas,MaxMatch());
}
return 0;
}
PS：还是注意 优化那个 如果当前节点被标记过并且是最后一个 匹配点，该条路就一定不能成为增广路！
京公网安备 11010502036488号