[二分枚举+匈牙利]hdoj 2236：无题II

大致题意：
    在一个n*n的矩阵中，找n个数使得这n个数都在不同的行和列里并且要求这n个数中的最大值和最小值的差值最小。

 

大致思路：

    看到了“最大最小”其实就应该想到是要用二分。这道题也是如此，首先二分枚举这个最大差值，再枚举下限，用匈牙利算法来验证枚举是否成立即可。但是这样做依然会tle，所以要加入一个辅助数组，来记录哪些数字曾经出现过，从而在枚举下界的时候可以避开那些无用的数字。

 

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=104;
const int mMax=105;
const int inf=1<<30;
int n,m;
int map[nMax][nMax];
bool vis[mMax];
int linkk[mMax];

int dfs(int s){
    for(int i=1;i<=m;i++){
        if(!vis[i]&&map[s][i]){
            vis[i]=1;
            if(linkk[i]==-1||dfs(linkk[i])){
                linkk[i]=s;
                return 1;
            }
        }
    }
    return 0;
}
bool app[101];
int num[nMax][nMax],sma,big;
bool check(int mid){
    int i,j,ans;
    for(int k=sma;k+mid<=big;k++){  //枚举下界
        if(!app[k])continue;
        ans=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(num[i][j]>=k&&num[i][j]<=k+mid){
                    map[i][j]=1;
                }else {
                    map[i][j]=0;
                }
                  //  cout<<map[i][j];
            }//cout<<endl;
        }
        memset(linkk,-1,sizeof(linkk));
        for(i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
            if(ans==n)return 1;
        }
    }
    return 0;
}

int main(){
    int i,j,cas,ans;
    scanf("%d",&cas);
    while(cas--){
        sma=inf;
        big=-1;
        scanf("%d",&n);
        m=n;
        memset(app,0,sizeof(app));
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                scanf("%d",&num[i][j]);
                sma=min(num[i][j],sma);
                big=max(num[i][j],big);
                app[num[i][j]]=1;
            }
        }
        int left=0,right=big-sma+1,mid;//开始二分
        while(right>=left){
            mid=(right+left)/2;
            if(check(mid)){
                right=mid-1;
                ans=mid;
            }
            else{
                left=mid+1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}