题解最优的挤奶方案(Optimal Milking)

最优的挤奶方案(Optimal Milking)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

农场主 John 将他的 K(1≤K≤30)个挤奶器运到牧场，在那里有 C(1≤C≤200)头奶牛，在奶

牛和挤奶器之间有一组不同长度的路。K个挤奶器的位置用1～K的编号标明，奶牛的位置用K+1～

K+C 的编号标明。

每台挤奶器每天最多能为 M(1≤M≤15)头奶牛挤奶。

编写程序，寻找一个方案，安排每头奶牛到某个挤奶器挤奶，并使得 C 头奶牛需要走的所有

路程中的最大路程最小。每个测试数据中至少有一个安排方案。每条奶牛到挤奶器有多条路。

输入

第 1 行为 3 个整数 K、C 和 M。

第 2～K+C+1 行，每行有 K+C 个整数，描述了奶牛和挤奶器（二者合称实体）之间的位置，

这 K+C 行构成了一个沿对角线对称的矩阵。第 2 行描述了第 1 个挤奶器离其他实体的距离，…，

第 K+1 行描述了第 K 个挤奶器离其他实体的距离；第 K+2 行描述了第 1 头奶牛离其他实体的距

离，…。这些距离为不超过 200 的正数。实体之间如果没有直接路径相连，则距离为 0。实体与

本身的距离（即对角线上的整数）也为 0。

输出

输出一个整数，为所有方案中，C 头奶牛需要走的最大距离的最小值。

样例输入

2 3 2

0 3 2 1 1

3 0 3 2 0

2 3 0 1 0

1 2 1 0 2

1 0 0 2 0

样例输出

题解：

又是一道网络流套二分的题目。

1.先用floyd求一个最短路map。

2.每一次虚拟一个源点和挤奶器建边，虚拟一个汇点和奶牛建边。

3.Dinic跑起来！！！

4.然后。。。就没有然后了。。。

AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<stack>

#include<ctime>

#include<vector>

using namespace std;

int n,m,l,s;

int map[][],cap[][],depth[];

int read()

{

    int ans=,f=;

    char i=getchar();

    while(i<''||i>''){if(i=='-')f=-;i=getchar();}

    while(i>=''&&i<=''){ans=ans*+i-'';i=getchar();}

    return ans*f;

}

bool bfs()

{

    memset(depth,,sizeof(depth));

    int b[],head=,tail=,i;

    b[tail++]=;

    depth[]=;

    while(head!=tail)

    {

        int x=b[head++];

        for(i=; i<=s+; i++)

        {

            if(depth[i]==&&cap[x][i]>)

            {

                depth[i]=depth[x]+;

                b[tail++]=i;

            }

        }

    }

    if(depth[s+]!=)return ;

    else return ;

}

int dfs(int root,int flow)

{

    if(root==s+)return flow;

    int res=;

    for(int i=; i<=s+; i++)

    {

        if(cap[root][i]>&&depth[i]==depth[root]+)

        {

            int tmp=dfs(i,min(flow-res,cap[root][i]));

            cap[root][i]-=tmp;

            cap[i][root]+=tmp;

            res+=tmp;

            if(res==flow)return flow;

        }

    }

    return res;

}

bool judge(int mid)

{

    memset(cap,,sizeof(cap));

    int i,j,k;

    for(i=; i<=n; i++)

        cap[][i]=l;

    for(i=; i<=n; i++)

        for(j=n+; j<=s; j++)

            if(map[i][j]<=mid)

                cap[i][j]=;

    for(i=n+; i<=s; i++)

        cap[i][s+]=;

    int root=,f=;

    while(bfs())

    {

        f+=dfs(root,);

    }

    return f>=m;

}

int main()

{

    int i,j,k;

    n=read();

    m=read();

    l=read();

    s=n+m;

    for(i=; i<=s; i++)

        for(j=; j<=s; j++)

        {

            map[i][j]=read();

            if(map[i][j]==)map[i][j]=2e8;

        }

    for(k=; k<=s; k++)

        for(i=; i<=s; i++)

            for(j=; j<=s; j++)

                if(i!=j&&j!=k&&k!=i&&map[i][k]+map[k][j]<map[i][j])

                    map[i][j]=map[i][k]+map[k][j];

    int l=,r=,ans=;

    while(l<=r)

    {

        int mid=(l+r)>>;

        if(judge(mid))

        {

            ans=mid;

            r=mid-;

        }

        else l=mid+;

    }

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

    return ;

}

总结：

1.最大值不能赋太大，否则会溢出。

2.最好还是用非递归的Dinic。

挤奶