传送门

描述

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

输入

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

输出

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

样例

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

Output
3

题解

找到最大差值maxsub，最小差值0，最大值maxnum，最小值minnum，二分差值找答案。

以行、列为顶点构建二分图，对于每个差值midsub=(maxsub+minsub)/2,令g从minsum遍历到g+midsub<=maxnum,在每个区间[g,g+midsub]里面找二分图最大匹配，（匹配点权值均在区间内）；

如果在区间里能找到n个匹配，则说明最小差值<=midsub，找差值左区间，同时保存这个差值；

否则说明最小差值>=midsub，找差值右区间；

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include
         
           #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long using namespace std; const int inf=0x3f3f3f3f; const int maxn=1e2+7; const int mod=1e9+7; int line[maxn][maxn],vis[maxn],match[maxn]; int n,minnum,maxnum,minsub,maxsub,midsub,p; bool Find(int x){
            for(int i=1;i<=n;i++){
                if(!vis[i]&&line[x][i]>=p&&line[x][i]<=p+midsub){
                    vis[i]=1;             if(!match[i]||Find(match[i])){
                        match[i]=x;                 return true;             }         }     }     return false; } bool Hungary(){
            int ans=0;     for(int i=1;i<=n;i++){
                INIT(vis,0);         if(!Find(i)) return false;     }     return true; } int main(){
            int t;     scanf("%d",&t);     while(t--){
                INIT(match,0);         minnum=inf,maxnum=-inf;         scanf("%d",&n);         for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        scanf("%d",&line[i][j]);                 minnum=min(minnum,line[i][j]);                 maxnum=max(maxnum,line[i][j]);             }         }         minsub=0,maxsub=maxnum-minnum;         int ans=0;         while(minsub<=maxsub){
                    midsub=(minsub+maxsub)/2;             int flag=0;             for(p=minnum;p+midsub<=maxnum;p++){
                        INIT(match,0);                 if(Hungary()) {
                            flag=1;                     break;                 }             }             if(flag)maxsub=midsub-1,ans=midsub;             else minsub=midsub+1;         }         printf("%d\n",ans);     } 	return 0; }

转载地址：https://blog.csdn.net/cpongo3/article/details/89334299 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

传送门

描述

输入

输出

样例

题解

Code

发表评论

最新留言

关于作者

推荐文章