[二分枚举+匈牙利]hdoj 2236：无题II
大致题意：
? ??在一个n*n的矩阵中，找n个数使得这n个数都在不同的行和列里并且要求这n个数中的最大值和最小值的差值最小。
?
大致思路：
? ? 看到了“最大最小”其实就应该想到是要用二分。这道题也是如此，首先二分枚举这个最大差值，再枚举下限，用匈牙利算法来验证枚举是否成立即可。但是这样做依然会tle，所以要加入一个辅助数组，来记录哪些数字曾经出现过，从而在枚举下界的时候可以避开那些无用的数字。
?
?
#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int nMax=104;const int mMax=105;const int inf=1<<30;int n,m;int map[nMax][nMax];bool vis[mMax];int linkk[mMax];int dfs(int s){ for(int i=1;i<=m;i++){ if(!vis[i]&&map[s][i]){ vis[i]=1; if(linkk[i]==-1||dfs(linkk[i])){ linkk[i]=s; return 1; } } } return 0;}bool app[101];int num[nMax][nMax],sma,big;bool check(int mid){ int i,j,ans; for(int k=sma;k+mid<=big;k++){ //枚举下界 if(!app[k])continue; ans=0; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(num[i][j]>=k&&num[i][j]<=k+mid){ map[i][j]=1; }else { map[i][j]=0; } // cout<<map[i][j]; }//cout<<endl; } memset(linkk,-1,sizeof(linkk)); for(i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; if(ans==n)return 1; } } return 0;}int main(){ int i,j,cas,ans; scanf("%d",&cas); while(cas--){ sma=inf; big=-1; scanf("%d",&n); m=n; memset(app,0,sizeof(app)); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ scanf("%d",&num[i][j]); sma=min(num[i][j],sma); big=max(num[i][j],big); app[num[i][j]]=1; } } int left=0,right=big-sma+1,mid;//开始二分 while(right>=left){ mid=(right+left)/2; if(check(mid)){ right=mid-1; ans=mid; } else{ left=mid+1; } } printf("%d\n",ans); } return 0;}