HDU2236 无题II 二分匹配+二分枚举
设vmin为矩阵中最小元素，设vmax为矩阵中最大元素，那么答案肯定在（0~vmax-vmin）之间，所以可以二分枚举差值，再在每一个差值里面枚举长度为这个差值的区间，若在该差值的区间内存在最大匹配数 更新二分区间的 right,否则更新left；
这道题目做的时候一直超时，后来改改就不超时了，现在还不知道为什么呢，看来大家做法都是大差不差的，
不过这道题目其实有一个很淫荡的做法，因为x,n的范围都不超过100，也可以不用管矩阵里面的最大值最小值，直接枚举0~100也是可以的，不会超时，没有去尝试
#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;vector<int>G[1212];int tempmp[1212];int mp[1212][1212];int marry[1212];bool vis[1212];int vmax,vmin,l,r,mid;int dis[2][4]={0,-1,0,1,1,0,-1,0};int n,m,k;void clear(){memset(marry,-1,sizeof(marry));memset(vis,false,sizeof(vis));memset(mp,0,sizeof(mp));for(int i=0;i<1212;i++)G[i].clear();}bool dfs(int x){for(int i=1;i<=n;i++){if(mp[x][i]>=k && mp[x][i]<=k+mid && !vis[i]){vis[i]=true;if(marry[i]==-1 || dfs(marry[i])){marry[i]=x;return 1;}}}return 0;}int main(void){int t;cin>>t;while(t--){clear();cin>>n;vmin=200,vmax=-1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>mp[i][j];if(mp[i][j]>vmax)vmax=mp[i][j];if(mp[i][j]<vmin)vmin=mp[i][j];}}r=vmax-vmin;//算出矩阵元素的最大差值l=0;bool flag=false;while(1)//二分枚举{mid=(l+r)/2;for(k=vmin;k+mid<=vmax;k++){flag=false;memset(marry,-1,sizeof(marry));for(int j=1;j<=n;j++){memset(vis,false,sizeof(vis));if(!dfs(j)){flag=true;break;}}if(!flag)//若存在最大匹配直接跳出break;}if(!flag)//若存在最大匹配更新rightr=mid;if(l==mid)break;if(flag)//否则更新leftl=mid;}cout<<r<<endl;}}