Description

【问题描述】
有N(1 <= N <= 1000) 头牛，M (1 <= M <= 20)个牛圈。
每头牛对于牛圈都有不同的喜好值(最喜欢为1，最不喜欢为B）。牛圈有一定的容量。
现在分配每头牛到牛圈去，要求所有牛的最大喜好值与最低喜好值的差值最小。输出最小的“喜好值差”加1。
【输入格式】
第一行N和M
下来N行，每行M个数。表示喜欢的牛圈的序号，按喜欢的程度（递减）给出，比如第一个给出的牛圈的就是最喜欢，最后一个就是最不喜欢的。 
下来M个数，每个数表示牛圈最多容纳的牛的数目。
【输出格式】
输出最小的“喜好值差”加1。
【样例输入】
6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2
【样例输出】
2

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=1100,M=51100;
struct edge{int x,y,f,pre;}a[M];int alen,last[N],cur[N];;
void ins(int x,int y,int f)
{
    ++alen;a[alen]=edge{x,y,f,last[x]};last[x]=alen;
    ++alen;a[alen]=edge{y,x,0,last[y]};last[y]=alen;
}
int h[1100],st,ed;
bool bfs()
{
    deque<int>Q;Q.clear();
	memset(h,0,sizeof(h));h[st]=1;
    Q.push_back(st);
    while(!Q.empty())
    {
        int x=Q.front();Q.pop_front();
        for(int k=last[x];k;k=a[k].pre)if(a[k].f)
        {
            int y=a[k].y;
            if(h[y]==0)
            {
                h[y]=h[x]+1;
                Q.push_back(y);
            }
        }
}
return h[ed]&gt;0;

}
int dinic(int x,int f)
{
if(xed)return f;
int sx=0;
for(int k=cur[x];k;k=a[k].pre)if(a[k].f)
{
cur[x]=k;
int y=a[k].y;
if(h[y]h[x]+1)
{
int sy=dinic(y,min(a[k].f,f-sx));
a[k].f-=sy;a[k^1].f+=sy;
sx+=sy;if(sxf) return f;
}
}
if(sx0)h[x]=0;
return sx;
}
int n,m,p[N][25],B[25];
bool check(int mid)
{
st=n+m+1;ed=n+m+2;
for (int L=1;L<=m-mid+1;L++)
{
int R=L+mid-1;
alen=1;memset(last,0,sizeof(last));
for (int i=1;i<=n;i++) ins(st ,  i , 1   );
for (int i=1;i<=m;i++) ins(n+i, ed , B[i]);
for (int i=1;i<=n;i++)
for (int j=L;j<=R;j++)
ins(i,n+p[i][j],1);
    int s=0;
    while(bfs())
    {
    	memcpy(cur&#44;last&#44;sizeof(last));
        s+=dinic(st&#44;1&lt;&lt;30);
    }
    if(s==n)return 1;
}
return 0;

}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&p[i][j]);
for (int i=1;i<=m;i++)scanf("%d",&B[i]);
int L=1,R=m,ans=-1;
while(L<=R)
{
int mid=(L+R)/2;
if (check(mid)==1)ans=mid,R=mid-1;
else                      L=mid+1;
}
printf("%d\n",ans);
return 0;
}

</p>