poj 2112二分+floyd+最大流好題

この問題の意味はK個の搾乳機械とC個の牛があり、1個の機械が毎日最大W個の乳牛にサービスし、牛と機械を頂点と見なすと2つの頂点の間の距離を教えてくれるなら、乳牛が搾乳に行くときの道の最大値を最小化してください.まずfloydを使って乳牛がある搾乳機械に行く最短の経路を求めることができます.それから2分1つの答え、図を建てて、私达は更に1つのスーパーソース点とスーパー送金点を定义して、ソース点は机械を指して、重み値はWで、机械と乳牛の间にも辺があって、条件を満たす辺の长さは2分以下の答えで、重み値は1で、各乳牛から送金点まで1つの辺の重み値は1で、この図の最大の流れはそれが乳牛の数に等しいかどうかを観察して、コードは次のとおりです.

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

using namespace std;
int K, C, M;
int d[250][250];

const int maxn = 500;
const int inf = 0x3f3f3f3f;

struct Dinic
{
    int n;       //n   
    struct edge
    {
        int from, to, cap;
    };
    vector<int> G[maxn];
    vector<edge> e;
    int level[maxn], iter[maxn];

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

    void add_edge(int u, int v, int cap)
    {
        e.push_back((edge)
        {
            u, v, cap
        });
        e.push_back((edge)
        {
            v, u, 0
        });
        int m = e.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }

    void bfs(int s)
    {
        memset(level, -1, sizeof(level));
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty())
        {
            int u = que.front();
            que.pop();
            for(int i=0; i<G[u].size(); i++)
            {
                edge &te = e[G[u][i]];
                if(te.cap>0 && level[te.to]<0)
                {
                    level[te.to] = level[u] + 1;
                    que.push(te.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f)
    {
        if(v == t) return f;
        for(int &i=iter[v]; i<G[v].size(); i++)
        {
            edge &tpe = e[G[v][i]];
            if(tpe.cap>0 && level[v]<level[tpe.to])
            {
                int d = dfs(tpe.to, t, min(f, tpe.cap));
                if(d > 0)
                {
                    tpe.cap -= d;
                    e[G[v][i]^1].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int max_flow(int s, int t)
    {
        int flow = 0;
        for(;;)
        {
            bfs(s);
            if(level[t]<0) return flow;
            memset(iter, 0, sizeof(iter));
            int f;
            while((f=dfs(s, t, 0x3fffffff)) > 0)
                flow += f;
        }
    }
} di;

void floyd()
{
    int n = K+C;
    for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}

bool check(int mid)
{
    di.n = K+C+2;   //0     machine 1-K cow K+1-K+C  K+C+1    
    di.init();
    for(int i=1; i<=K; i++)       //  
    {
        for(int j=1+K; j<=C+K; j++)   if(d[i][j]<=mid) //  
        {
            int u=i, v=j;
            di.add_edge(u, v, 1);
        }
        di.add_edge(0, i, M);
    }
    for(int j=1; j<=C; j++) di.add_edge(K+j, K+C+1, 1);
    int f = di.max_flow(0, K+C+1);
    return f==C;
}

int main()
{
    while(scanf("%d%d%d", &K, &C, &M)==3)
    {
        for(int i=1; i<=K+C; i++)
            for(int j=1; j<=K+C; j++)
            {
                scanf("%d", &d[i][j]);
                if(i!=j && d[i][j]==0) d[i][j] = inf;
            }
        floyd();
        int l=0, r=100000;
        int ans;

        while(l <= r)
        {
            int mid = (l+r)/2;
            if(check(mid))
            {
                ans = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        printf("%d
", ans);
    }
    return 0;
}