nx一个挤奶器，ny奶牛，每个挤奶罐为最m奶牛使用。

现在给nx+ny在矩阵之间的距离。要求使所有奶牛挤奶到挤奶正在旅程，最小的个体奶牛步行距离的最大值。

始感觉这个类似二分图匹配，不同之处在于挤奶器能够连接m个以内的奶牛，用网络流的模型是能够求出满足条件的解的。

问题是怎样满足最大路程的最小值，这一种典型的二分的问法。。

所以我们二分答案，也就是枚举最大路程，直到求得最小值。

每次建边既加入全部最大路程以内的边，加入源点向每一个挤奶器建边。容量为m。其它边都是1，

若返回的最大流是ny则该枚举值能够达到。

这题由于二分上界wa的是由于 有些点之间開始不直接连通，求了floyd之后联通了且边权>200

#include <iostream>

#include <cstring>

#include <string>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#define inf 0x3f3f3f3f

#define eps 1e-6

#define ll __int64

const int maxn=300;

using namespace std;

int n,s,t,level[maxn],c[maxn][maxn];

int m,nx,ny,dis[maxn][maxn];

bool makelevel()

{

    memset(level,0,sizeof level);

    level[s]=1;

    int q[maxn];

    int fro=0,iq=0;

    q[iq++]=s;

    int i,v;

    while(fro!=iq)

    {

        v=q[fro++];

        for(i=0;i<=n+1;i++)//注意点的编号

        {

            if(!level[i]&&c[v][i])

            {

                level[i]=level[v]+1;

                q[iq++]=i;

            }

        }

    }

    if(!level[t]) return 0;

    return 1;

}

int dfs(int now,int maxf)

{

    if(now==t) return maxf;

    int ret=0;

    for(int i=0;maxf&&i<=n+1;i++)//注意点的编号

    {

        if(c[now][i]&&level[now]+1==level[i])

        {

            int tmp=dfs(i,min(maxf,c[now][i]));

            c[now][i]-=tmp;

            c[i][now]+=tmp;

            ret+=tmp;

            maxf-=tmp;

        }

    }

    return ret;

}

int dinic(int d)

{

    int i,j;

    memset(c,0,sizeof c);

    for(i=1;i<=nx;i++)

    {

        c[s][i]=m;

        for(j=nx+1;j<=n;j++)

        {

            c[j][t]=1;

            if(dis[i][j]<=d) c[i][j]=1;

        }

    }

    int ans=0;

    while(makelevel()) ans+=dfs(s,inf);

    return ans;

}

int main()

{

    int a,mmax,ri,le,mid,i,j,k;

    while(~scanf("%d%d%d",&nx,&ny,&m))

    {

        mmax=0;

        n=nx+ny;

        s=0;t=n+1;

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

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

            {

                scanf("%d",&a);

                if(j>nx&&i<=nx) mmax=max(mmax,a);

                dis[i][j]=(a==0?inf:a);

            }

        for(k=1;k<=n;k++)

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

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

                {

                    if(i!=j&&dis[i][j]>dis[i][k]+dis[k][j])

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

                }

        ri=10000;

        le=0;

        while(le<ri)

        {

            mid=(le+ri)/2;

            if(dinic(mid)>=ny)

                ri=mid;

            else le=mid+1;

        }

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

    }

    return 0;

}