hdu 2236

题目：

Problem Description

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

Input

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

Output

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

分析：要在不同行不同列中找n个数，很容易想到用二分匹配。但是要这n个数的最大值和最小值的差值最小就比较麻烦了。其实，这个时候应该要想想枚举的方法能不能做得出这个题目了。枚举差值，再在每一个差值里面枚举长度为这个差值的区间。在枚举差值的过程还能用二分法来加速，若在该差值的限制下找到符合题意的匹配就将差值的枚举范围缩为[min,mid]，否则缩为[mid,max]。

View Code

 1 #include<cstdio>
 2 int mat[2][100],nx,ny,vmax,vmin,min,max,mid,p;
 3 bool visited[100],matrix[100][100];
 4 int path(int u)
 5 {
 6     int i;
 7     for(i=0;i<ny;i++)
 8     {
 9         if(matrix[u][i]>=p && matrix[u][i]<=p+mid && !visited[i])
10         {
11             visited[i]=true;
12             if(mat[1][i]==-1 || path(mat[1][i]))
13             {
14                 mat[0][u]=i;
15                 mat[1][i]=u;
16                 return 1;
17             }
18         }
19     }
20     return 0;
21 }
22 bool Hungary()
23 {
24     int i,j;
25     for(i=0;i<nx;i++)
26         mat[0][i]=-1;
27     for(i=0;i<ny;i++)
28         mat[1][i]=-1;
29     for(i=0;i<nx;i++)
30     {
31         for(j=0;j<ny;j++)
32             visited[j]=false;
33         if(path(i)==0)
34             return false;
35     }
36     return true;
37 }
38 int main()
39 {
40     int t;
41     scanf("%d",&t);
42     while(t--)
43     {
44         scanf("%d",&nx);
45         ny=nx;
46         vmax=0;
47         vmin=0xffffff;
48         for(int i=0;i<nx;i++)
49         {
50             for(int j=0;j<ny;j++)
51             {
52                 scanf("%d",&matrix[i][j]);
53                 if(matrix[i][j]>vmax)
54                     vmax=matrix[i][j];
55                 if(matrix[i][j]<vmin)
56                     vmin=matrix[i][j];
57             }
58         }
59         max=vmax-vmin;
60         min=0;
61         while(true)
62         {
63             mid=(min+max)/2;
64             bool flag=false;
65             for(p=vmin;p+mid<=vmax;p++)
66             {
67                 if(Hungary())
68                 {
69                     flag=true;
70                     break;
71                 }
72             }
73             if(flag)
74                 max=mid;
75             if(mid==min)
76                 break;
77             if(!flag)
78                 min=mid;
79         }
80         printf("%d\n",max);
81     }
82     return 0;
83 }