POJ2112-Optimal Milking(二分答案+Floyd+网络流)

题目链接:POJ2112-Optimal Milking

题意:

k台挤奶机,编号为1-k,c只奶牛,编号为k+1-k+c,一台机器可以工作m只奶牛,然后给出奶牛,挤奶机互相之间的距离,奶牛要去挤奶机那挤奶,问走最远的奶牛需要走的最小距离。

题解:

二分答案+floyed+网络流。

先用floyd预处理出任意两点之间的最短距离,然后二分答案mid,把图中距离大于mid的边全部舍弃,距离小于等于mid的边建流量为1的边,然后跑网络流进行检测,检测条件为最大流是否等于奶牛数量,

参考代码:

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 250;
const int inf = 1000000;
int k, c, m, n;
int mp[MAXN][MAXN];
struct EDGE
{
    int v, nxt, w;
} edge[MAXN * MAXN];
int cnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
void buildgraph(int x)
{
    cnt = 0;
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= k; i++)
    {
        addedge(i, n + 1, m);
        addedge(n + 1, i, 0);
    }
    for (int i = k + 1; i <= n; i++)
    {
        addedge(0, i, 1);
        addedge(i, 0, 0);
    }
    for (int i = 1; i <= k; i++)
        for (int j = k + 1; j <= n; j++)
            if (mp[i][j] <= x)
                addedge(j, i, 1), addedge(i, j, 0);
}
int depth[MAXN], cur[MAXN], gap[MAXN];
void bfs(int st, int ed)
{
    memset(gap, 0, sizeof(gap));
    memset(depth, -1, sizeof(depth));
    depth[ed] = 0, gap[0] = 1;
    queue<int> que;
    while (!que.empty())
        que.pop();
    que.push(ed);
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            if (depth[v] != -1)
                continue;
            que.push(v);
            depth[v] = depth[u] + 1;
            gap[depth[v]]++;
        }
    }
    return;
}
int dfs(int u, int flow, int st, int ed)
{
    if (u == ed)
        return flow;
    int tot = 0;
    for (int &i = cur[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if (w && depth[v] + 1 == depth[u])
        {
            int di = dfs(v, min(flow - tot, w), st, ed);
            if (di)
            {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                tot += di;
            }
            if (tot == flow)
                return flow;
        }
    }
    gap[depth[u]]--;
    if (gap[depth[u]] == 0)
        depth[st] = n + 3;
    depth[u]++;
    gap[depth[u]]++;
    return tot;
}
int ISAP(int st, int ed)
{
    int sum = 0;
    bfs(st, ed);
    while (depth[st] < n + 2)
    {
        for (int i = 0; i <= n + 1; i++)
            cur[i] = fir[i];
        sum += dfs(st, inf, st, ed);
    }
    return sum;
}
int main()
{
    while (scanf("%d%d%d", &k, &c, &m) != EOF)
    {
        n = k + c;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                scanf("%d", &mp[i][j]);
                if (i != j && !mp[i][j])
                    mp[i][j] = inf;
            }
        for (int t = 1; t <= n; t++)
            for (int u = 1; u <= n; u++)
                for (int v = 1; v <= n; v++)
                    if (mp[u][v] > mp[u][t] + mp[t][v])
                        mp[u][v] = mp[u][t] + mp[t][v];
        int l = 1, r = inf, ans = inf;
        while (l < r)
        {
            int mid = (l + r) / 2;
            buildgraph(mid);
            int check = ISAP(0, n + 1);
            if (check == c)
            {
                r = mid;
                ans = mid;
            }
            else
                l = mid + 1;
        }
        printf("%d\n", ans);
    }

    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。