链接：点击打开链接

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

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int s[105][105],match[105],vis[105];

int n,p,low,high,mid,minn,maxx;

int dfs(int x){

    int i;

    for(i=1;i<=n;i++){

        if(s[x][i]>=p&&s[x][i]<=p+mid&&!vis[i]){

            vis[i]=1;

            if(!match[i]||dfs(match[i])){

                match[i]=x;

                return 1;

            }

        }

    }

    return 0;

}

int hungarian(){

    int i;

    memset(match,0,sizeof(match));

    for(i=1;i<=n;i++){

    memset(vis,0,sizeof(vis));

    if(!dfs(i))

    return 0;

    }

    return 1;

}                                       //匈牙利算法模板

int main(){                             //要求不同行不同列因此用到二分图最大匹配看是否全部的

    int t,i,j,sign;                     //数据在指定区间中

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        memset(s,0,sizeof(s));

        maxx=-1;minn=99999999;

        for(i=1;i<=n;i++)

        for(j=1;j<=n;j++){

            scanf("%d",&s[i][j]);

            maxx=max(maxx,s[i][j]);

            minn=min(minn,s[i][j]);

        }

        high=maxx-minn;low=0;           //二分差值的大小

        while(low<high){

            sign=0;

            mid=(low+high)/2;

            for(p=minn;p+mid<=maxx;p++){//看是否完美匹配时全部数据满足在[p,p+mid]范围内

                if(hungarian()){

                    sign=1;

                    break;

                }

            }

            if(sign)

            high=mid;                   //满足时则改变high值看能否继续满足更小的区间

            if(!sign)

            low=mid+1;

        }

        printf("%d\n",high);

    }

    return 0;

}