【最大匹配+二分答案】HDU 2236 无题II

题目内容

这是一个简单的游戏，在一个(n×n)的矩阵中，找(n)个数使得这(n)个数都在不同的行和列里并且要求这(n)个数中的最大值和最小值的差值最小。

输入格式

输入一个整数(T)，表示(T)组数据。
对于每组数据第一行输入一个正整数(n(1le nle 100))表示矩阵的大小。
接着输入(n)行，每行(n)个数(x(0le xle 100))。

输出格式

对于每组数据输出一个数表示最小差值。

样例输入

1
4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

样例输出

3

思路

对于找出来的(n)个数，均属于区间([l,r]),那么答案就是(r-l)。所以枚举区间然后进行二分图匹配，让所有可能的匹配权值都属于这个区间即可。
二分图最大匹配+二分答案。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=100+10;
const int INF=0x3f3f3f3f;
int n,ans,Min,Max;
int g[maxn][maxn],match[maxn];
bool vis[maxn];

bool Find(int u){
    for(int i=1;i<=n;i++){
        if(!vis[i]&&g[u][i]>=Min&&g[u][i]<=Max){
            vis[i]=1;
            if(!match[i]||Find(match[i])){
                match[i]=u;
                return true;
            }
        }
    }
    return false;
}

bool judge(){
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));//这里记得初始化下
        if(!Find(i))
            return false;
    }
    return true;
}

int main(){
    int T,minl,maxr;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        maxr=0;minl=INF;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&g[i][j]);
                minl=min(g[i][j],minl);
                maxr=max(g[i][j],maxr);//找到左右边界
            }
        }

        int l=0;
        int r=maxr-minl;//注意所求的答案是最小差值
        ans=0;
        while(l<=r){
            bool flag=false;
            int mid=(l+r)/2;

            for(int i=minl;i+mid<=maxr;i++){
                Min=i;Max=i+mid;
                if(judge()){
                    flag=true;
                    break;
                }
            }

            if(flag){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        printf("%d
",ans);
    }

    return 0;
}