不知道为什么今天的题都要嘲讽我这个做不出“简单”游戏的蒟蒻
题意：给你一个n*n的方阵，从中选出n个数，且每行每列最多选一个，求选出的数中最大值和最小值的差，并是这个差最小。
思路:和上次的题读起来有些相似之处，但这道题并不需要KM算法，由于每行每列只能选一个数，我们直接跑匈牙利算法求出匹配即可，关于最小差的问题呢？我们可以每次枚举我们二分图匹配时边权的取值范围，只有边权在这个范围内时我们才考虑将两点进行匹配，那么我们的答案就是当区间最小且完成匹配时的区间长度，单是直接枚举区间长度会超时间，于是我们采用二分的方法进行优化。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 const int N=250; 6 const int Inf=0x3f3f3f3f; 7 using namespace std; 8 int n,match[N],p,l,r,mid,g[N][N],vis[N]; 9 int dfs(int x){ 10 for(int i=1;i<=n;++i){ 11 if(p<=g[x][i]&&g[x][i]<=p+mid&&!vis[i]){ 12 vis[i]=1; 13 if(!match[i]||dfs(match[i])){ 14 match[i]=x; 15 return 1; 16 } 17 } 18 } 19 return 0; 20 } 21 bool work(){ 22 int ans=0; 23 memset(match,0,sizeof(match)); 24 for(int i=1;i<=n;++i){ 25 memset(vis,0,sizeof(vis)); 26 if(dfs(i)) ans++; 27 } 28 return ans==n?1:0; 29 } 30 int main(){ 31 int t,Max,Min; 32 scanf("%d",&t); 33 while(t--){ 34 Max=-Inf; 35 Min=Inf; 36 scanf("%d",&n); 37 for(int i=1;i<=n;++i) 38 for(int j=1;j<=n;++j){ 39 scanf("%d",&g[i][j]); 40 Max=max(Max,g[i][j]);//用于求出最大区间长度 41 Min=min(Min,g[i][j]); 42 } 43 l=0;r=Max-Min;//r是最大区间长度 44 int ans=0; 45 while(l<=r){//二份枚举 46 int cnt=0; 47 mid=((l+r)>>1); 48 for(p=Min;p+mid<=Max;++p){ 49 if(work()){//当前情况成立 50 cnt=1; 51 break; 52 } 53 } 54 if(cnt){//记录答案 55 ans=mid; 56 r=mid-1; 57 } 58 else l=mid+1; 59 } 60 printf("%d ",ans); 61 } 62 return 0; 63 }