题目
https://www.luogu.com.cn/problem/P2857
思路
直接思考不太好处理，也没有对应的模型可以套。那么我们考虑枚举最终答案，并通过一个check函数判断答案的可行性。
枚举区间跨度还不够，我们还需要枚举区间起点，这样，原问题就变成：能否找到一个分配方案，使每头牛的对所属牛棚的评价（就这么说吧，原题说法太拗口）属于([l,r])这个区间。
考虑牛与牛棚的关系，如果牛(i)对棚(j)的评价在([l,r])区间内，那么(i)可以放入(j)，否则不行。简而言之，就是:有N个物体，B个盒子，已知每个物体只能放入哪些盒子，求是否能将所有物体放入盒子。
那么问题就简单了，我们把牛与棚看成结点，如果牛(i)可以放入棚(j)，那么在(i)与(j)间连一条有向边。建个源点，汇点，跑最大流，检验最大流是否为N就可以了。
虽说要枚举的次数不多，但是check函数的复杂度巨大，建议还是二分区间长度吧。
至于check函数，学长说可以用Hopcroft-Karp，但我感觉用现学的算法写非模板题不太好，就还是用了O(玄学)的dinic，仍然能过233.
注意事项：输入很坑，第(i+1)行第(j)列并不表示牛棚(j)在牛(i)眼里的位次，而是代表在牛(i)眼里位次为(j)的棚的序号！！！
代码
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
int num[21],Rank[1001][21],n,m,S,T;
int fst[1200],nxt[41000],cnt=0,deep[1200];
struct edge{
int u,v,cap;
} e[41000];
int inv(int x){
if(x&1) return x+1;
else return x-1;
}
void add(int x,int y,int z){
e[++cnt].u=x;
e[cnt].v=y;
e[cnt].cap=z;
nxt[cnt]=fst[x];
fst[x]=cnt;
}
void build(int l,int r){
int i,j;
S=n+m+1;T=n+m+2;cnt=0;
memset(fst,0,sizeof(fst));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(Rank[i][j]>=l&&Rank[i][j]<=r){
add(i,n+j,1);
add(n+j,i,0);
}
}
}
for(i=1;i<=n;i++){
add(S,i,1);
add(i,S,0);
}
for(i=1;i<=m;i++){
add(n+i,T,num[i]);
add(T,n+i,0);
}
}
int bfs(){
queue<int> q;
int i,flag=0;
memset(deep,0,sizeof(deep));
q.push(S);deep[S]=1;
while(!q.empty()){
int p=q.front();
if(p==T) flag=1;
for(i=fst[p];i;i=nxt[i]){
if(deep[e[i].v]||!e[i].cap) continue;
deep[e[i].v]=deep[p]+1;
q.push(e[i].v);
}
q.pop();
}
return flag;
}
int dfs(int x,int flow){
int i;
if(x==T) return flow;
for(i=fst[x];i;i=nxt[i]){
if(deep[e[i].v]==deep[x]+1){
if(e[i].cap){
int tmp=dfs(e[i].v,min(flow,e[i].cap));
if(tmp){
e[i].cap-=tmp;
e[inv(i)].cap+=tmp;
return tmp;
}
}
}
}
return 0;
}
int dinic(){
int i,ans=0;
while(bfs()){
int flow;
while(flow=dfs(S,inf)){
ans+=flow;
}
}
return ans;
}
bool check(int x){
int i,j,k;
for(i=1;i+x<=m;++i){
build(i,i+x);
if(dinic()==n) return true;
}
return false;
}
int main(){
int i,j,x;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
scanf("%d",&x);
Rank[i][x]=j;
}
}
for(i=1;i<=m;++i)
scanf("%d",&num[i]);
int l=0,r=m-1;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d",l+1);
// system("pause");
return 0;
}