题意:有n头牛,B个谷场，牛对每个谷场的喜爱都有不同的排名，每个谷场承受牛的上限，然后求这些放置后这些牛对这些谷场的排名范围大小最小。
题解:二分范围大小mid，然后求每个范围牛是否能否多重匹配成功即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int mx = 1e3+5; int g[mx][mx]; int lim[mx]; int vis[mx]; int len[mx],y[mx][mx]; int N,B; bool find(int u,int l,int r){ for(int i = l; i <= r; i++){ int v = g[u][i]; if(!vis[v]){ vis[v] = 1; if(len[v]<lim[v]){ y[v][len[v]++] = u; return true; } for(int j = 0; j < len[v]; j++) if(find(y[v][j],l,r)){ y[v][j] = u; return true; } } } return false; } bool MaxMatch(int l,int r){ memset(len,0,sizeof(len)); for(int i = 1; i <= N; i++){ memset(vis,0,sizeof(vis)); if(!find(i,l,r)) return false; } return true; } bool check(int len){ for(int i = 1; i+len-1<=B; i++) if(MaxMatch(i,i+len-1)) return true; return false; } int main(){ while(scanf("%d%d",&N,&B)!=EOF){ for(int i = 1; i <= N; i++) for(int j = 1; j <= B; j++) scanf("%d",&g[i][j]); for(int i = 1; i <= B; i++) scanf("%d",&lim[i]); int l = 1,r = B; while(l<r){ int mid = (l+r)/2; if(check(mid)) r = mid; else l = mid+1; } printf("%d\n",r); } return 0; }