POJ 2112 Optimal Milking 二分最大流

时间：2014-02-25 16:57:24 收藏：0 阅读：412

Optimal Milking

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 10887		Accepted: 3946
Case Time Limit: 1000MS

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

* Line 1: A single line with three space-separated integers: K, C, and M.

* Lines 2.. ...: Each of these K+C lines of K+C space-separated integers describes the distances between pairs of various entities. The input forms a symmetric matrix. Line 2 tells the distances from milking machine 1 to each of the other entities; line 3 tells the distances from machine 2 to each of the other entities, and so on. Distances of entities directly connected by a path are positive integers no larger than 200. Entities not directly connected by a path have a distance of 0. The distance from an entity to itself (i.e., all numbers on the diagonal) is also given as 0. To keep the input lines of reasonable length, when K+C > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line.

Output

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

Sample Input

Sample Output

Source

USACO 2003 U S Open

有k个挤奶机，m头牛，给出它们之间的相互距离，每个挤奶机能够容纳k头牛，问在挤奶机容纳所有的牛的情况下，牛到挤奶机的最短距离是多少。

首先题目给出的距离不一定是最短距离，所以要用floyd算法求出所有点之间的最短距离。

然后建图，源点和挤奶机相连，容量为挤奶机能够容纳的奶牛数，牛与汇点相连，容量为1，这个比较容易想到，那么挤奶机和牛要怎么连接呢？

题目求的是最短距离，所以咱们可以从图中最长的距离枚举到0，这样求出的肯定是最短距离，枚举肯定超时，不如就二分，效率还高，既然二分的话，距离也肯定一次比一次小，那么要使挤奶机和奶牛相连的话，它们之间的距离必须要小于二分后的距离，最后求出的距离肯定是最短的。

//808K	94MS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 10000000
#define M 1007
#define MIN(a,b) a>b?b:a;
using namespace std;
struct E
{
    int v,w,next;
}edg[500000];
int dis[2000],gap[2000],head[2000],nodes;
int sourse,sink,nn;

int g[307][307],n,m,k,max_dis,s,t;
void addedge(int u,int v,int w)
{
    edg[nodes].v=v;
    edg[nodes].w=w;
    edg[nodes].next=head[u];
    head[u]=nodes++;
    edg[nodes].v=u;
    edg[nodes].w=0;
    edg[nodes].next=head[v];
    head[v]=nodes++;
}
int dfs(int src,int aug)
{
    if(src==sink)return aug;
    int left=aug,mindis=nn;
    for(int j=head[src];j!=-1;j=edg[j].next)
    {
    	int v=edg[j].v;
    	if(edg[j].w)
        {
           if(dis[v]+1==dis[src])
           {
               int minn=MIN(left,edg[j].w);
               minn=dfs(v,minn);
               edg[j].w-=minn;
               edg[j^1].w+=minn;
               left-=minn;
               if(dis[sourse]>=nn)return aug-left;
               if(left==0)break;
           }
           if(dis[v]<mindis)
           mindis=dis[v];
        }
    }

        if(left==aug)
        {
            if(!(--gap[dis[src]]))dis[sourse]=nn;
            dis[src]=mindis+1;
            gap[dis[src]]++;
        }
        return aug-left;
}
int sap(int s,int e)
{
    int ans=0;
	nn=e+1;
    memset(dis,0,sizeof(dis));
    memset(gap,0,sizeof(gap));
    gap[0]=nn;
    sourse=s;
    sink=e;
    while(dis[sourse]<nn)
    ans+=dfs(sourse,inf);
    return ans;
}
void floyd()
{
    for(int k=1;k<t;k++)
        for(int i=1;i<t;i++)
            for(int j=1;j<t;j++)
                if(g[i][j]>g[i][k]+g[k][j])
                    g[i][j]=g[i][k]+g[k][j];
}
bool build(int mid)
{
    memset(head,-1,sizeof(head));
    nodes=0;
    for(int i=1;i<=n;i++)
        addedge(s,i,k);
    for(int i=1;i<=m;i++)
        addedge(n+i,t,1);
    for(int i=1;i<=n;i++)
        for(int j=1+n;j<t;j++)//这个地方忘记+n，错了一下午
            if(g[i][j]<=mid)
                addedge(i,j,1);
    if(sap(s,t)>=m)return true;
    return false;
}
int solve()
{
    int l=0,r=max_dis,mid,ans;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(build(mid)){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    return ans;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        s=0,t=n+m+1;
        max_dis=0;
        for(int i=1;i<t;i++)
            for(int j=1;j<t;j++)
            {
                scanf("%d",&g[i][j]);
                if(!g[i][j])g[i][j]=inf;
            }
        floyd();
        for(int i=1;i<t;i++)
            for(int j=1;j<t;j++)
                if(g[i][j]!=inf)
                    max_dis=max(max_dis,g[i][j]);
        int anss=solve();
        printf("%d\n",anss);
    }
    return 0;
}

原文：http://blog.csdn.net/crescent__moon/article/details/19837751