终于自己独立做出来一道题QAQ然而本校数据实在太水不能确定我是不是写对了。。。
原题：
Farmer John的N(1<=N<=1000)头奶牛分别居住在农场所拥有的B(1<=B<=20)个牛棚的某一个里。有些奶牛很喜欢她们当前住的牛棚，而另一些则讨厌再在它们现在所在的牛棚呆下去。
FJ在忍受了若干次奶牛的抱怨后，决定为所有奶牛重新安排牛棚，使最不满的那头奶牛与最高兴的奶牛的心情差异最小，即使这会让所有奶牛都更加郁闷。
每头奶牛都把她对各个牛棚的好感度从高到低排序后告诉了FJ。当然，如果一头奶牛被安排到的牛棚在她给出的列表中越靠后，她就会越郁闷。你可以认为奶牛的郁闷指数是她被分配到的牛棚在列表中的位置。奶牛们是斤斤计较的，她们无法容忍别的奶牛在自己喜欢的牛棚里快乐地生活，而自己却呆在一个自己不喜欢的牛棚里。每个牛棚都只能容纳一定数量的奶牛。FJ希望在每个牛棚都没有超出容量限制的前提下，使最郁闷和最高兴的奶牛的郁闷指数的跨度最小。
FJ请你帮他写个程序，来计算这个最小的郁闷指数跨度到底是多少。
刚学网络流来看着道题的时候感觉根本没思路啊，现在再回来看已经能解决掉了（也许是数据实在太水……
要求使最大值与最小值的差最小，有点二分的意思？，因为郁闷值的范围很小（1-n）所以可以枚举最小的，二分最大的
然后根据枚举和二分出的两个值建图，源到每头牛流量1，设a[i][j]为第i头牛郁闷值为j的房间，x为枚举的最小，y为二分的最大，第i头牛就与a[i][x~y]流量为1，每个房间到汇流量为房间容量
然后跑最大流，如果能跑到满流，说明方案合法继续二分
数据太水，不好验证这样做是否正确，应该是正确的吧= =
终于自己做出来一道题了好开心OvO
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int oo=;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
struct ddd{int y,v,re;}; vector <ddd> e[];
inline void ist(int x,int y,int z){
e[x].push_back((ddd){y,z,e[y].size()});
e[y].push_back((ddd){x,,e[x].size()-});
}
int n,m,a[][],b[]; int s,t;
int ans=oo;
int lvl[];
int q[],hd=;
void otmp(int x){
cout<<x<<endl;
for(int i=;i<e[s].size();++i) cout<<s<<"->"<<e[s][i].y<<" "<<e[s][i].v<<endl;
for(int i=;i<=n;++i)for(int j=;j<e[i].size();++j)if(e[i][j].y>n)
cout<<i<<"->"<<e[i][j].y-n<<" "<<e[i][j].v<<endl;
for(int i=;i<=m;++i)for(int j=;j<e[i].size();++j)if(e[i][j].y==t)
cout<<i<<"->"<<t<<" "<<e[i][j].v<<endl;
}
bool gtlvl(){
memset(lvl,,sizeof(lvl));
q[hd=]=s,lvl[s]=;
int x,sz;
for(int k=;k<=hd;++k){
x=q[k],sz=e[x].size();
for(int i=;i<sz;++i)if(e[x][i].v && !lvl[e[x][i].y])
lvl[e[x][i].y]=lvl[x]+,q[++hd]=e[x][i].y;
}
return lvl[t];
}
int agmt(int x,int y){
if(x==t) return y;
int mxflw=,flw,sz=e[x].size();
for(int i=;i<sz && mxflw<y;++i)if(lvl[e[x][i].y]==lvl[x]+)
if(flw=agmt(e[x][i].y,min(y-mxflw,e[x][i].v))){
mxflw+=flw;
e[x][i].v-=flw,e[e[x][i].y][e[x][i].re].v+=flw;
}
if(!mxflw) lvl[x]=;
return mxflw;
}
int dnc(){
int bwl=,flw;
while(gtlvl())while(flw=agmt(s,oo)){
//otmp(flw);
bwl+=flw;
}
return bwl;
}
bool chck(int x,int y){
for(int i=s;i<=t;++i) e[i].clear();
for(int i=;i<=m;++i) ist(i+n,t,b[i]);
for(int i=;i<=n;++i) ist(s,i,);
for(int i=;i<=n;++i)for(int j=x;j<=y;++j)
ist(i,a[i][j]+n,);
//otmp(y-x+1+1000);
return dnc()==n;
}
int bnrsch(int x){
int l=,r=m-x,md;
if(!chck(x,x+r)) return oo;
while(l+<r){
md=(l+r)>>;
(chck(x,x+md)?r:l)=md;
}
return (chck(x,x+l)?l:r)+;
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n>>m; s=,t=n+m+;
for(int i=;i<=n;++i)for(int j=;j<=m;++j) a[i][j]=rd();
for(int i=;i<=m;++i) b[i]=rd();
for(int i=;i<=m;++i) ans=min(ans,bnrsch(i));
cout<<ans<<endl;
return ;
}