这是一道最大匹配+二分答案的题目。首先，二分差值，上下界为0和最大值与最小值的差。然后匈牙利算法求能否匹配，可以的话减小差值，不能的话增加差值。代码：
#include<cstdio> #include<cstring> #define maxn 101 int n,l,r,mid,p; int w[maxn][maxn]; int match[maxn]; bool vis[maxn]; bool dfs(int u) { for(int v=1;v<=n;v++) if(w[u][v]>=p&&w[u][v]<=p+mid&&!vis[v])//由p和p+mid来决定选不选 { vis[v]=1; if(match[v]==-1||dfs(match[v])) { match[v]=u;return true; } } return false; } bool maxmatch()//匈牙利算法 { memset(match,-1,sizeof match); for(int i=1;i<=n;i++) { memset(vis,0,sizeof vis); if(!dfs(i))return false; } return true; } int main() {int T; scanf("%d",&T); while(T--) { int mn=100,mx=0; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&w[i][j]), mn=(mn>w[i][j])?w[i][j]:mn, mx=(mx<w[i][j])?w[i][j]:mx; l=0,r=mx-mn;int res; while(l<=r)//二分答案 { mid=(l+r)>>1;bool f=false; for(p=mn;p+mid<=mx;p++)//枚举p为取出的数中最小的一个,p+mid为最大的一个 if(maxmatch()) { f=true;break; } if(f)res=mid,r=mid-1; else l=mid+1; } printf("%d\n",res); } }
