poj2112 Optimal Milking [最大流+Floyd+二分]

in 题目 with 0 comment

Description

FJ has moved his K (1 <= K <= 30) milking machines out into the cow pastures among the C (1 <= C <= 200) cows. A set of paths of various lengths runs among the cows and the milking machines. The milking machine locations are named by ID numbers 1..K; the cow locations are named by ID numbers K+1..K+C.

Each milking point can "process" at most M (1 <= M <= 15) cows each day.

Write a program to find an assignment for each cow to some milking machine so that the distance the furthest-walking cow travels is minimized (and, of course, the milking machines are not overutilized). At least one legal assignment is possible for all input data sets. Cows can traverse several paths on the way to their milking machine.


Input


Output

A single line with a single integer that is the minimum possible total distance for the furthest walking cow.


Sample Input

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


Sample Output

2


Source

USACO 2003 U S Open


Solution

首先分析题目,题目要求找到奶牛要走最大距离的最小值,我们考虑可以二分答案,枚举可能的最小值,每次只有距离小于等于这个值的时候才连边,对新建的图跑一次最大流,比较与C的大小关系,若>C则说明最小值还可以更小,否则最小值大一点.于是我们只要事先用floyd求出任意两点之间的最短路径即可


Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 250
#define INF 100005
//#define DEBUG 
using namespace std;
int k,c,m,n;
int lev[maxn];
int dis[maxn][maxn],Map[maxn][maxn];

inline int read()
{
    char ch;
    int read=0,sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0' && ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar();
    } 
    return sign*read;
} 

void floyd()
{
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            if(dis[i][k]!=INF)
                for(int j=1;j<=n;++j)
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

void build_graph(int Min)
{
    memset(Map,0,sizeof(Map));
    for(int i=k+1;i<=n;++i) Map[0][i]=1;
    for(int i=1;i<=k;++i) Map[i][n+1]=m;
    for(int i=k+1;i<=n;++i)
        for(int j=1;j<=k;++j)
            if(dis[i][j]<=Min)
                Map[i][j]=1; 
}

bool bfs()
{
    memset(lev,-1,sizeof(lev));
    queue<int> q;
    q.push(0);
    lev[0]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=0;i<=n+1;++i)
            if(lev[i]<0&&Map[u][i])
            {
                lev[i]=lev[u]+1;
                q.push(i);
            }
    }
    if(lev[n+1]==-1) return 0;
    return 1;
}

int dfs(int x,int flow)
{
    int w,used=0;
    if(x==n+1) return flow;
    for(int i=0;i<=n+1;++i)
        if(Map[x][i]&&lev[i]==lev[x]+1)
        {
            w=flow-used;
            w=dfs(i,min(w,Map[x][i]));
            Map[x][i]-=w;
            Map[i][x]+=w;
            used+=w;
            if(used==flow) return flow;
        }
    if(!used) lev[x]=-1;
    return used;
}

int dinic(int Min)
{
    int ans=0;
    build_graph(Min);
    while(bfs()) ans+=dfs(0,INF);
    return ans;
}

int main()
{
    k=read(),c=read(),m=read(),n=k+c;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            dis[i][j]=read();
            if(!dis[i][j]) dis[i][j]=INF;
        }
    floyd();
    int l=0,r=10000;
    while(l<r)
    {
        int mid=(l+r)/2;
        int ans=dinic(mid);
        if(ans>=c) r=mid;
        else l=mid+1;
    }
    printf("%d\n",r);
    return 0;
} 

扫描二维码,在手机上阅读!
Responses