HDU_2236
为了保证每行每列只取一个元素，我们可以从二分图最大匹配的思想入手，把行和列分别看做二分图左右两部分，i-j的边权就是第i行第j列的元素的值。这样构图之后，求得的二分图最大匹配的4条边就是不在同行或同列的4个元素。
有了这个思想时候，我们只需要再保证4个元素中最大值与最小值之差尽量小就可以了，于是我们可以二分枚举最大值与最小值之差，并枚举边权值的下界，如果枚举到某个边权值的下界时该图存在最大匹配，那么就更新max，否则就更新min。
#include<stdio.h>
#include<string.h>
int n,G[110][110],xM[110],yM[110],check[110];
int max,min,mid,gmin,gmax,p;
int searchpath(int u)
{
int v;
for(v=0;v<n;v++)
if(G[u][v]>=p&&G[u][v]<=p+mid&&!check[v])
{
check[v]=1;
if(yM[v]==-1||searchpath(yM[v]))
{
yM[v]=u;
xM[u]=v;
return 1;
}
}
return 0;
}
int judge()
{
int i;
memset(xM,-1,sizeof(xM));
memset(yM,-1,sizeof(yM));
for(i=0;i<n;i++)
{
memset(check,0,sizeof(check));
if(!searchpath(i))
return 0;
}
return 1;
}
int main()
{
int i,j,k,T,t,ok;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
gmin=100;
gmax=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&G[i][j]);
if(G[i][j]<gmin)
gmin=G[i][j];
if(G[i][j]>gmax)
gmax=G[i][j];
}
max=gmax-gmin;
min=0;
while(1)
{
mid=(min+max)/2;
ok=0;
for(p=gmin;p+mid<=gmax;p++)
if(judge())
{
ok=1;
break;
}
if(ok)
max=mid;
if(mid==min)
break;
if(!ok)
min=mid;
}
printf("%d\n",max);
}
return 0;
}