HDU 2236（无题II） 二分匹配（匈牙利，HK）+二分查找

对x，y轴进行二分匹配，然后二分差值，枚举最小值。当一个枚举的一个最小值使其能够得到完美匹配时，表示这个差值是可行的。

下面给出匈牙利算法和HK算法的代码。

1.匈牙利

#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x7ffffff
using namespace std;
const int N=100+5;
int map[N][N],n,k,mid;
int vis[N],link[N];
void Init()
{
memset(map,-1,sizeof(map));
}
bool dfs(int u)
{
for(int i=0;i<n;i++)
{
if(!vis[i]&&map[u][i]>=k&&k+mid>=map[u][i])
{
vis[i]=1;
if(link[i]==-1||dfs(link[i]))
{
link[i]=u;
return true;
}
}
}
return false;
}
bool match()
{
memset(link,-1,sizeof(link));
for(int i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
if(!dfs(i)) 
{
return false;
}
}
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
Init();
int Min=inf,Max=-inf;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&map[i][j]);
if(Min>map[i][j]) Min=map[i][j];
if(Max<map[i][j]) Max=map[i][j];
}
}
int cha=Max-Min;
int lft=0,rht=cha;
while(lft<rht)
{
int mark=0;
mid=(lft+rht)>>1;
for(k=Min;k+mid<=Max;k++)
{
if(match())
{
mark=1;
break;
}
}
if(mark) rht=mid;
else lft=mid+1;
}
printf("%d\n",lft);
}
return 0;
}

2.HK

#include<stdio.h>
#include<string.h>
#include<queue>
#define inf 0x7ffffff
#define N 100+5 
using namespace std;
int n,map[N][N];
int mmax,mmin,cha,k;
int linkx[N],linky[N],dx[N],dy[N],vis[N],dis;
int spath()
{
queue<int>q;
dis=inf;
while(!q.empty()) q.pop();
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));

for(int i=1;i<=n;i++)
if(linkx[i]==-1)
{
dx[i]=0;
q.push(i);
}
while(!q.empty())
{
int u=q.front(); 
q.pop();
if(dis<dx[u]) break;
for(int v=1;v<=n;v++)
{
if(dy[v]==-1&&map[u][v]>=k&&map[u][v]<=k+cha)
{
dy[v]=dx[u]+1;
if(linky[v]==-1) dis=dy[v]; 
else
{
dx[linky[v]]=dy[v]+1;
q.push(linky[v]);
}
}
}
}
return dis!=inf;
}
int dfs(int u)
{
for(int v=1;v<=n;v++)
{
if(!vis[v]&&dy[v]==dx[u]+1)
if(map[u][v]>=k&&map[u][v]<=cha+k)
{
vis[v]=1;
if(linky[v]!=-1&&dis==dy[v]) continue;
if(linky[v]==-1||dfs(linky[v]))
{
linkx[u]=v;
linky[v]=u;
return 1;
}
}
}
return 0;
}
int match()
{
int res=0;
memset(linkx,-1,sizeof(linkx));
memset(linky,-1,sizeof(linky));
while(spath())
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
if(linkx[i]==-1)
res+=dfs(i);
}
return res==n;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
mmax=-inf;mmin=inf;
memset(map,-1,sizeof(map));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]<mmin) mmin=map[i][j];
if(map[i][j]>mmax) mmax=map[i][j];
}
cha=mmax-mmin;
int low=0,high=cha;
while(low<high)
{
int mark=0;
cha=(low+high)/2;
for(k=mmin;k<=mmax-cha;k++)
{
if(match())
{
    mark=1;break;
}
}
if(mark) high=cha;
else low=cha+1;
}
printf("%d\n",low);
}
return 0;
}