hdu2236 无题II 最大匹配 + 二分搜索

中文题目，题意大家都明白。

看到“不同的行和列”就觉得要用二分匹配来做。要求最大值与最小值的差值最小，是通过枚举边的下限和上限来完成。

枚举过程是这样的，在输入的过程可以记录下边权的最大值MAX和最小值MIN。那么他们的边权的差值的最大值为right = MAX -MIN ,最小值left =0。然后不断地增加边的下限，查找边权的差值，如果能得到完美匹配（匹配数等于n）,那么就记录下这个差值。最后输出。这个搜索过程类似于最大流+二分搜索。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=105,INF=0x3f3f3f3f;
int Map[N][N],cx[N],cy[N],dx[N],dy[N];
bool bmask[N],bmap[N][N];
int nx,ny,dis,ans;
bool searchpath()
{
    queue<int> q;
    dis=INF;
    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    for(int i=1;i<=nx;i++)
    {
        if(cx[i]==-1){ q.push(i); dx[i]=0; }
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            if(dx[u]>dis) break;
            for(int v=1;v<=ny;v++)
            {
                if(bmap[u][v]&&dy[v]==-1)
                {
                    dy[v]= dx[u] + 1;
                    if(cy[v]==-1) dis=dy[v];
                    else
                    {
                        dx[cy[v]]= dy[v]+1;
                        q.push(cy[v]);
                    }
                }
            }
        }
    }
    return dis!=INF;
}
int findpath(int u)
{
    for(int v=1;v<=ny;v++)
    {
        if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1)
        {
            bmask[v]=1;
            if(cy[v]!=-1&&dy[v]==dis) continue;
            if(cy[v]==-1||findpath(cy[v]))
            {
                cy[v]=u; cx[u]=v;
                return 1;
            }
        }
    }
    return 0;
}
void maxmatch()
{
    ans=0;
    memset(cx,-1,sizeof(cx));
    memset(cy,-1,sizeof(cy));
    while(searchpath())
    {
        memset(bmask,0,sizeof(bmask));
        for(int i=1;i<=nx;i++)
            if(cx[i]==-1) ans+=findpath(i);
    }
}
void init()
{
    memset(bmap,0,sizeof(bmap));
}

int main()
{
    //freopen("test.txt","r",stdin);
    int i,j,k,n,cas,a,b;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        a=100,b=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++){
                scanf("%d",&Map[i][j]);
                a=min(a,Map[i][j]);
                b=max(b,Map[i][j]);
            }
        nx=ny=n;
        int L=0,R=b-a,mid,flag,res;
        while(L<=R)
        {
            mid=(L+R)/2;
            flag=0;
            for(k=a;k<=b;k++)
            {
                for(i=1;i<=n;i++)
                    for(j=1;j<=n;j++)
                        if(Map[i][j]>=k&&Map[i][j]<=k+mid) bmap[i][j]=1;
                        else bmap[i][j]=0;
                maxmatch();
                if(ans==n) {flag=1;break;}
            }
            if(flag) {res=mid;R=mid-1;}
            else  L=mid+1;
        }
        printf("%d\n",res);
    }
    return 0;
}