题意: 表示题意看不懂,不够最后自己YY出来了。
简化一下题意可以如下描述:
给一个N*B的矩阵,N是牛的数量,B是牛舍的数量,每头牛对应一个牛舍序列(偏好是骗人的,不用管),每个牛舍有个容量C[i].
再给两个指针l,r.指向矩阵的两列(l<=r),现在规定l,r确定后,这些牛只能住进[l,r]中间区域的牛舍,问是否可以安排?如果可以,问r-l+1最小值是多少。
做法:网络流。这个枚举的思想很巧妙,反正我自己是想不到。。。
如果某个[l,r]区间可以安排的话那么[l,r+1] to [l,b]肯定可以安排。所以应该l++;
否则r++;
这题值得再研究下.
int n,b;
//牛[0,n-1]
//棚[n,n+b-1]
//超级源[n+b]
//超级汇[n+b+1]
//共n+b+2个结点
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;
}