终于自己独立做出来一道题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
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<vector> 7 using namespace std; 8 const int oo=168430090; 9 int rd(){int z=0,mk=1; char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} 11 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} 12 return z*mk; 13 } 14 struct ddd{int y,v,re;}; vector <ddd> e[1100]; 15 inline void ist(int x,int y,int z){ 16 e[x].push_back((ddd){y,z,e[y].size()}); 17 e[y].push_back((ddd){x,0,e[x].size()-1}); 18 } 19 int n,m,a[1100][30],b[1100]; int s,t; 20 int ans=oo; 21 int lvl[1100]; 22 int q[1100],hd=0; 23 void otmp(int x){ 24 cout<<x<<endl; 25 for(int i=0;i<e[s].size();++i) cout<<s<<"->"<<e[s][i].y<<" "<<e[s][i].v<<endl; 26 for(int i=1;i<=n;++i)for(int j=0;j<e[i].size();++j)if(e[i][j].y>n) 27 cout<<i<<"->"<<e[i][j].y-n<<" "<<e[i][j].v<<endl; 28 for(int i=1;i<=m;++i)for(int j=0;j<e[i].size();++j)if(e[i][j].y==t) 29 cout<<i<<"->"<<t<<" "<<e[i][j].v<<endl; 30 } 31 bool gtlvl(){ 32 memset(lvl,0,sizeof(lvl)); 33 q[hd=1]=s,lvl[s]=1; 34 int x,sz; 35 for(int k=1;k<=hd;++k){ 36 x=q[k],sz=e[x].size(); 37 for(int i=0;i<sz;++i)if(e[x][i].v && !lvl[e[x][i].y]) 38 lvl[e[x][i].y]=lvl[x]+1,q[++hd]=e[x][i].y; 39 } 40 return lvl[t]; 41 } 42 int agmt(int x,int y){ 43 if(x==t) return y; 44 int mxflw=0,flw,sz=e[x].size(); 45 for(int i=0;i<sz && mxflw<y;++i)if(lvl[e[x][i].y]==lvl[x]+1) 46 if(flw=agmt(e[x][i].y,min(y-mxflw,e[x][i].v))){ 47 mxflw+=flw; 48 e[x][i].v-=flw,e[e[x][i].y][e[x][i].re].v+=flw; 49 } 50 if(!mxflw) lvl[x]=0; 51 return mxflw; 52 } 53 int dnc(){ 54 int bwl=0,flw; 55 while(gtlvl())while(flw=agmt(s,oo)){ 56 //otmp(flw); 57 bwl+=flw; 58 } 59 return bwl; 60 } 61 bool chck(int x,int y){ 62 for(int i=s;i<=t;++i) e[i].clear(); 63 for(int i=1;i<=m;++i) ist(i+n,t,b[i]); 64 for(int i=1;i<=n;++i) ist(s,i,1); 65 for(int i=1;i<=n;++i)for(int j=x;j<=y;++j) 66 ist(i,a[i][j]+n,1); 67 //otmp(y-x+1+1000); 68 return dnc()==n; 69 } 70 int bnrsch(int x){ 71 int l=0,r=m-x,md; 72 if(!chck(x,x+r)) return oo; 73 while(l+1<r){ 74 md=(l+r)>>1; 75 (chck(x,x+md)?r:l)=md; 76 } 77 return (chck(x,x+l)?l:r)+1; 78 } 79 int main(){//freopen("ddd.in","r",stdin); 80 cin>>n>>m; s=0,t=n+m+1; 81 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) a[i][j]=rd(); 82 for(int i=1;i<=m;++i) b[i]=rd(); 83 for(int i=1;i<=m;++i) ans=min(ans,bnrsch(i)); 84 cout<<ans<<endl; 85 return 0; 86 }