学步园

题意：

有K台挤奶机器和C头牛(统称为物体），每台挤奶机器只能容纳M头牛进行挤奶。现在给出dis[K + C][K + C]的矩阵，dis[i][j]若不为0则表示第i个物体到第j个物体之间有路，dis[i][j]就是该路的长度。（1 <= K <= 30,1 <= C <= 200）

现在问你怎么安排这C头牛到K台机器挤奶，使得需要走最长路程到挤奶机器的奶牛所走的路程最少，求出这个最小值。

分析：

利用Floyd算法求出每个奶牛到每个挤奶机的最短距离。
则题目变为：
已知C头奶牛到K个挤奶机的距离，每个挤奶机只能有M个奶牛，每个奶牛只能去一台挤奶机，求这些奶牛到其要去的挤奶机距离的最大值的最小值。

每个奶牛最终都只能到达一个挤奶器，每个挤奶器只能有M个奶牛，可把奶牛看做网络流中的流。
每个奶牛和挤奶器都是一个节点，添加一个源，连边到所有奶牛节点，这些边容量都是1。
添加一个汇点，每个挤奶器都连边到它。这些边的容量都是M。

先假定一个最大距离的的最小值 maxdist, 在上述图中，如果奶牛节点i和挤奶器节点j之间的距离<= maxdist,则从i节点连一条边到j节点，表示奶牛i可以到挤奶器j去挤奶。该边容量为1。该图上的最大流如果是C(奶牛数），那么就说明假设的 maxdist成立，则减小 maxdist再试
总之，要二分 maxdist, 对每个maxdist值，都重新构图，看其最大流是否是C，然后再决定减少或增加maxdist

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 500 + 5;
const int INF = 100000000;
struct Edge{
    int from, to, cap, flow;
};

struct Dinic{
    int n, m, s, t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n)
    {
        this->n = n;
        for(int i=0; i<=n; ++i) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, int cap)
    {
        edges.push_back((Edge){from, to, cap, 0});
        edges.push_back((Edge){to, from, 0, 0});
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis, 0, sizeof vis );
        queue<int> Q;
        Q.push(s);
        vis[s] = 1;
        d[s] = 0;
        while(!Q.empty())
        {
            int x = Q.front(); Q.pop();
            for(int i=0; i<G[x].size(); ++i)
            {
                Edge& e = edges[G[x][i]];
                if(!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a)
    {
        if(x == t || a == 0) return a;
        int flow = 0, f;
        for(int& i = cur[x]; i<G[x].size(); ++i)
        {
            Edge& e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to] && (f=DFS(e.to, min(a,e.cap-e.flow)))>0)
            {
                e.flow += f;
                edges[G[x][i]^1].flow -= f;
                flow += f;
                a -= f;
                if(a==0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s, int t)
    {
        this->s = s; this->t =t;
        int flow = 0;
        while(BFS()){
            memset(cur, 0, sizeof cur );
            flow += DFS(s, INF);
        }
        return flow;
    }
};

int dis[maxn][maxn];
void floyd(int n)
{
    int i, j, k;
    for(k=1; k<=n; ++k)
    for(i=1; i<=n; ++i)
    for(j=1; j<=n; ++j)
    {
        if(i!=j && i!=k && j!=k &&dis[i][k]!=0 && dis[k][j]!=0)
        {
            if(dis[i][k] + dis[k][j]<dis[i][j] || dis[i][j]==0)
            {
                dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
}

Dinic solver;

int n, k, c, m;
bool ok(int  len)
{
    int now, i, j;
    solver.init(n+1);
    for(i=1; i<=k; ++i)
        for(j=k+1; j<=n; ++j)
            if(dis[i][j]<=len && dis[i][j] != 0)
                solver.AddEdge(j, i, 1); //牛与机器之间距离小于maxs的加一条容量为1的弧
    int s = 0, t = n+1;
    for(i=k+1; i<=n; ++i) //源点到每头牛设一条容量为1的弧
        solver.AddEdge(s, i, 1);
    for(i=1; i<=k; ++i)  //机器到汇点设一条容量为m的弧
        solver.AddEdge(i, t, m);

    int ans = solver.Maxflow(s, t);
    return (ans == c);
}
int main()
{
    int i, j;
    scanf("%d%d%d", &k, &c, &m);
    n = k + c;
    for(i=1; i<=n; ++i)
    for(j=1; j<=n; ++j)
    scanf("%d", &dis[i][j]);
    floyd(n);

    int l = 0, r = 0, mid;
    for(i=1; i<=k; ++i)
    for(j=k+1; j<=n; ++j)
        if(r < dis[i][j]) r = dis[i][j];

    while(l < r)
    {
        mid = (l+r) / 2;
        if( ok(mid))
            r = mid;
        else
            l = mid+1;
    }
    printf("%d\n", r);
    return 0;
}