无题II(二分+匈牙利)

传送门Poj1325

描述

这是一个简单的游戏,在一个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<bits/stdc++.h>
#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;
}
Donate comment here