The Fourth Dimension Space

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

POJ 2112 Optimal Milking 网络流+二分

越来越感觉网络流+二分还挺常见的啊,而且往往是要求一个最大的量最小的时候用。
题意:有K台机器,C头奶牛,他们之间的距离用一个邻接矩阵表示,每台机器能容纳M头奶牛喝奶。现在给这C头奶牛分配机器,满足两个要求:
1.这C头奶牛可以找到机器(这个条件由M限制)
2.C头奶牛中走的路程最长的奶牛 要让他的路程尽量短。
问这个最长距离的最小值(有点绕。。。)

做法:首先floyd一下,与处理处点对之间的最短路长度。
二分距离,保存原图中<=mid的边,添加超级源汇,s到每头牛建立容量是1的边,每台机器到t建立容量是M的边,跑一遍最大流,如果满流,说明C头牛都可以在mid的限制条件下被分配。取距离最小值即可.

模板就不贴了,构图如下:

int mat[maxn][maxn];
int K,C,M;
int n;//记录牛和机器的总数量
void input()
{
    scanf(
"%d%d%d",&K,&C,&M);
    n
=K+C;
    
for(int i=0;i<n;i++)
    
{

        
for(int j=0;j<n;j++)
        
{
            scanf(
"%d",&mat[i][j]);
            
if(mat[i][j]==0&&(i!=j))
                mat[i][j]
=INF;//表示不连通
        }

    }

}


void floyd()
{
    
for(int k=0;k<n;k++){
        
for(int i=0;i<n;i++){
            
for(int j=0;j<n;j++)
            
{
                
if(mat[i][k]!=INF&&mat[k][j]!=INF)
                
{
                    
if(mat[i][k]+mat[k][j]<mat[i][j])
                        mat[i][j]
=mat[i][k]+mat[k][j];
                }

            }

        }

    }

}



bool check(int mid)
{
    
int s=n;
    
int t=n+1;//公有n+2个结点
    
//
    for(int i=0;i<=t;i++)
        adj[i]
=NULL;
    len
=0;//重新构图

    
for(int i=K;i<n;i++)
    
{
        
for(int j=0;j<K;j++)
        
{
            
if(mat[i][j]<=mid)
            
{

                insert(i,j,
1);
            }

        }

    }

    
for(int i=K;i<n;i++)
        insert(s,i,
1);
    
for(int i=0;i<K;i++)
        insert(i,t,M);
    
return sap(t+1,s,t)==C;
}




int main()
{

    input();
    floyd();
    
int l=0;
    
int r=INF;
    
int ans=-1;
    
while(l<=r)
    
{
        
int mid=(l+r)>>1;
        
if(check(mid))
        
{
            r
=mid-1;
            ans
=mid;
        }

        
else
            l
=mid+1;
    }

    printf(
"%d\n",ans);



    
return 0;
}


PS:开始没搞清楚题目干嘛给邻接矩阵,那么多输入都是没用的东西。
不过倒是自然地帮你编了号。。。额。。。只要加个s,t,省事了。。。

posted on 2010-11-06 15:49 abilitytao 阅读(1544) 评论(0)  编辑 收藏 引用


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