The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3189 Steady Cow Assignment 网络流

题意: 表示题意看不懂,不够最后自己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;
}

posted on 2010-11-07 02:06 abilitytao 阅读(1210) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理