題意： 表示題意看不懂，不夠最后自己YY出來(lái)了。
簡(jiǎn)化一下題意可以如下描述：
給一個(gè)N*B的矩陣，N是牛的數(shù)量，B是牛舍的數(shù)量，每頭牛對(duì)應(yīng)一個(gè)牛舍序列（偏好是騙人的，不用管),每個(gè)牛舍有個(gè)容量C[i].
再給兩個(gè)指針l,r.指向矩陣的兩列(l<=r),現(xiàn)在規(guī)定l,r確定后，這些牛只能住進(jìn)[l,r]中間區(qū)域的牛舍，問(wèn)是否可以安排?如果可以,問(wèn)r-l+1最小值是多少。
做法：網(wǎng)絡(luò)流。這個(gè)枚舉的思想很巧妙，反正我自己是想不到。。。
如果某個(gè)[l,r]區(qū)間可以安排的話那么[l,r+1] to [l,b]肯定可以安排。所以應(yīng)該l++;
否則r++;
這題值得再研究下.
int n,b;
//牛[0,n-1]
//棚[n,n+b-1]
//超級(jí)源[n+b]
//超級(jí)匯[n+b+1]
//共n+b+2個(gè)結(jié)點(diǎn)
int a[maxn][25];
int c[25];
bool check(int l,int r)
{
for(int i=0;i<n+b+2;i++)
adj[i]=NULL;
len=0;
int s=0;
int t=n+b+1;
for(int i=1;i<=n;i++)
{
for(int j=l;j<=r;j++)
{
insert(i,n+a[i][j],1);
}
}
for(int i=1;i<=n;i++)
insert(s,i,1);
for(int i=1;i<=b;i++)
{
insert(n+i,t,c[i]);
}
if(dinic(n+b+2,s,t)==n)
return true;
else
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",&a[i][j]);
//
for(int i=1;i<=b;i++)
scanf("%d",&c[i]);
int l=1;
int r=1;
int ans=b;
while(l<=r&&r<=b)
{
if(ans==1)
break;
if(r-l+1>=ans)
{
l++;
continue;
}
if(check(l,r))
{
if((r-l+1)<ans)
ans=(r-l+1);
l++;
}
else
r++;
}
printf("%d\n",ans);
}
return 0;
}