<题目链接>
题目大意：
有n头牛，m个牛棚，每个牛棚都有一定的容量（就是最多能装多少只牛），然后每只牛对每个牛棚的喜好度不同（就是所有牛圈在每个牛心中都有一个排名），然后要求所有的牛都进牛棚，牛棚在牛心中的排名差计算方法为：所有牛中最大排名和最小排名之差+1(包括区间端点)。问最小的排名差。
解题分析：
先进行二分答案，二分枚举该区间等级的差值，然后根据枚举的区间差值找到所有的等级区间，判断这些等级区间中是否存在符合条件的。判断的依据就是个根据枚举的等级区间，对所有的牛和牛棚进行多重匹配，如果所有的牛都能够分配到牛棚中，则当前枚举的区间符合条件。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 1e3+;
struct Node{
int k,a[N]; //k代表牛棚当前的人数,a[N]存储牛棚中的所有人
}match[N];
int n,B,vis[N];
int G[N][N],capacity[N];
bool dfs(int u,int l,int r){
for(int i=;i<=B;i++){
if(!vis[i]&&G[u][i]>=l&&G[u][i]<=r){ //判断第i个牛棚在牛u心中的等级是否处于枚举的等级中
vis[i]=;
if(match[i].k<capacity[i]){ //如果该牛棚未满，则将牛u(暂时)分配到牛棚i中
match[i].a[++match[i].k]=u;
return true;
}
for(int j=;j<=match[i].k;j++){
if(dfs(match[i].a[j],l,r)){ //如果该牛棚已满，就枚举该牛棚中所有的牛，看他们是否能够找到其他能够分配的牛棚
match[i].a[j]=u; //如果能够找到的话，就用牛u来替代该牛的位置
return true;
}
}
}
}
return false;
}
bool Hungary(int l,int r){
memset(match,,sizeof(match));
for(int i=;i<=n;i++){
memset(vis,,sizeof(vis));
if(!dfs(i,l,r))return false; //只要有一只牛在当前枚举的区间内不能分配到牛棚中，就说明当前枚举的区间不合法
}
return true;
}
int main(){
while(scanf("%d%d",&n,&B)!=EOF){
memset(G,,sizeof(G));
for(int i=;i<=n;i++)
for(int j=;j<=B;j++){
int x;scanf("%d",&x);
G[i][x]=j; //第i头牛，对x牛棚的喜欢度是第j个等级
}
for(int i=;i<=B;i++)
scanf("%d",&capacity[i]); //每个牛棚的容量
int l=,r=B,ans=B;
while(l<=r){
int mid=(l+r)>>; //枚举区间最大等级与最小等级的差值
bool fp=false;
for(int i=;i<=B;i++){ //枚举区间的左端点，即该区间的最小等级
if(Hungary(i,i+mid)){ //判断在该等级范围内，是否满足条件
fp=true;break;
}
}
if(fp)ans=mid+,r=mid-; //ans记录的是该区间的大小，所以需要+1
else l=mid+;
}
printf("%d\n",ans);
}
}
2018-11-17