时间戳

首页 > 技术文章 > 题解 最优的挤奶方案(Optimal Milking)

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

huangdalaofighting 2017-05-09 14:20 原文

最优的挤奶方案(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

样例输出

2
题解：
又是一道网络流套二分的题目。
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[301][301],cap[301][301],depth[301];
int read()
{
    int ans=0,f=1;
    char i=getchar();
    while(i<'0'||i>'9'){if(i=='-')f=-1;i=getchar();}
    while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();}
    return ans*f;
}
bool bfs()
{
    memset(depth,0,sizeof(depth));
    int b[30001],head=0,tail=0,i;
    b[tail++]=0;
    depth[0]=1;
    while(head!=tail)
    {
        int x=b[head++];
        for(i=0; i<=s+1; i++)
        {
            if(depth[i]==0&&cap[x][i]>0)
            {
                depth[i]=depth[x]+1;
                b[tail++]=i;
            }
        }
    }
    if(depth[s+1]!=0)return 1;
    else return 0;
}
int dfs(int root,int flow)
{
    if(root==s+1)return flow;
    int res=0;
    for(int i=0; i<=s+1; i++)
    {
        if(cap[root][i]>0&&depth[i]==depth[root]+1)
        {
            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,0,sizeof(cap));
    int i,j,k;
    for(i=1; i<=n; i++)
        cap[0][i]=l;
    for(i=1; i<=n; i++)
        for(j=n+1; j<=s; j++)
            if(map[i][j]<=mid)
                cap[i][j]=1;
    for(i=n+1; i<=s; i++)
        cap[i][s+1]=1;
    int root=0,f=0;
    while(bfs())
    {
        f+=dfs(root,2000000000);
    }
    return f>=m;
}
int main()
{
    int i,j,k;
    n=read();
    m=read();
    l=read();
    s=n+m;
    for(i=1; i<=s; i++)
        for(j=1; j<=s; j++)
        {
            map[i][j]=read();
            if(map[i][j]==0)map[i][j]=2e8;
        }
    for(k=1; k<=s; k++)
        for(i=1; i<=s; i++)
            for(j=1; 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=0,r=5000000,ans=5000000;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

总结：

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

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

推荐阅读