题意：在一个n*n的矩阵中，找n个数使得这n个数都在不同的行和列里并且要求这n个数中的最大值和最小值的差值最小。
分析：刚学，刚做过类似题的二分图又来了
显然，应该把n行与n列之间建立一个二分图，但他这个题要求的是最大边与最小边的最小差值
这里能想到的是设定一个minp和一个maxp用来限制可选的边的边权
这样n²枚举出限制的范围，然后跑二分图即可，
但这样n²显然稍微有点难以接受
所以也能想到用二分
但这里二分也稍微有一点难度
应该把差值作为二分的东西，然后枚举上边界或者下边界，这样对应的下边界或者上边界也能求出来，这样的复杂度是nlgn
而不应该用某种奇怪的方法比如l，r分别表示minp和maxp（看起来复杂度好像直接变成lgn，实际上随便想想就会发现不行）
代码：
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=1e2+1; const int inf=0x3f3f3f3f; int mapp[maxn][maxn]; bool vis[maxn]; int girl[maxn]; int minx,maxx,n,nowl,nowr; int read() { char ch=getchar();int ans=0; while(ch>‘9‘||ch<‘0‘) ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) { ans=(ans<<1)+(ans<<3)+ch-‘0‘; ch=getchar(); } return ans; } int dfs(int x) { for(int i=1;i<=n;i++) { if(mapp[x][i]>=nowl&&mapp[x][i]<=nowr&&!vis[i]) { vis[i]=1; if(!girl[i]||dfs(girl[i])) { girl[i]=x; return 1; } } } return 0; } int chuli(int mid) { for(nowl=minx;nowl+mid<=maxx;nowl++) { nowr=nowl+mid; memset(girl,0,sizeof(girl)); int ans=0; for(int i=1;i<=n;i++) memset(vis,0,sizeof(vis)),ans+=dfs(i); if(ans==n) return 1; } return 0; } int main() { int t,x; t=read(); while(t--) { n=read(); minx=inf,maxx=-inf; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mapp[i][j]=read(),minx=min(minx,mapp[i][j]),maxx=max(maxx,mapp[i][j]); int l=0,r=maxx-minx; while(l<=r) { int mid=(l+r)/2; if(chuli(mid)) r=mid-1; else l=mid+1; } printf("%d\n",l); } return 0; }
原文：https://www.cnblogs.com/lin4xu/p/12873082.html