Gym - 101128F Landscaping（网络流）

题意

给你一个\(N×M\)的草地，有高地有低地。

收割机从低地走到高地或者从高地走到低地都要花费用\(A\)，你可以花费用\(B\)把一块高地变成低地，或者把一块低地变成高地。收割机每行每列都是必须要跑一趟的。

求最小花费。

解析

\(S\)向低地、高地向\(T\)建权为\(B\)的边，相邻的地之间建边权为\(A\)的边。

然后求最小割。

相同类型的地之间为什么也要建边呢？因为类型是可以改变的。

#include <bits/stdc++.h>

#define FOPI freopen("in.txt", "r", stdin)

#define FOPO freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

const int inf = 0x3f3f3f3f;

const int maxn = 50 * 50 + 1000;

const int maxm = 1e5 + 100;

struct Edge

{

    int to, next, cap, flow;

}edge[maxm];

int tot;

int head[maxn];

void init()

{

    tot = 2;

    memset(head, -1, sizeof(head));

}

void build(int u, int v, int w, int rw = 0)

{

    edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = 0;

    edge[tot].next = head[u]; head[u] = tot++;

    edge[tot].to = u; edge[tot].cap = 0; edge[tot].flow = 0;

    edge[tot].next = head[v]; head[v] = tot++;

}

int Q[maxn];

int dep[maxn], cur[maxn], sta[maxn];

bool bfs(int s, int t, int n)

{

    int front = 0, tail = 0;

    memset(dep, -1, sizeof(dep[0]) * (n+1));

    dep[s] = 0;

    Q[tail++] = s;

    while(front < tail)

    {

        int u = Q[front++];

        for (int i = head[u]; i != -1; i = edge[i].next)

        {

            int v = edge[i].to;

            if (edge[i].cap > edge[i].flow && dep[v] == -1)

            {

                dep[v] = dep[u] + 1;

                if (v == t) return true;

                Q[tail++] = v;

            }

        }

    }

    return false;

}

LL dinic(int s, int t, int n)

{

    LL maxflow = 0;

    while(bfs(s, t, n))

    {

        for (int i = 0; i < n; i++) cur[i] = head[i];

        int u = s, tail = 0;

        while(cur[s] != -1)

        {

            if (u == t)

            {

                int tp = inf;

                for (int i = tail-1; i >= 0; i--)

                    tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);

                //if (tp >= inf) return -1;

                maxflow += tp;

                for (int i = tail-1; i >= 0; i--)

                {

                    edge[sta[i]].flow += tp;

                    edge[sta[i]^1].flow -= tp;

                    if (edge[sta[i]].cap - edge[sta[i]].flow == 0) tail = i;

                }

                u = edge[sta[tail]^1].to;

            }

            else if (cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow

                     && dep[u]+1 == dep[edge[cur[u]].to])

            {

                sta[tail++] = cur[u];

                u = edge[cur[u]].to;

            }

            else

            {

                while(u != s && cur[u] == -1) u = edge[sta[--tail]^1].to;

                cur[u] = edge[cur[u]].next;

            }

        }

    }

    return maxflow;

}

int n, m, A, B;

int S, T;

char a[maxn][maxn];

int id(int i, int j) { return (i-1)*m + j; }

int main()

{

    //FOPI;

    init();

    scanf("%d%d%d%d", &n, &m, &A, &B);

    S = 0, T = n*m+1;

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

        for (int j = 1; j <= m; j++)

        {

            scanf(" %c", &a[i][j]);

            if (a[i][j] == '.') build(S, id(i, j), B);

                else build(id(i, j), T, B);

            if (i > 1) build(id(i, j), id(i-1, j), A);

            if (i < n) build(id(i, j), id(i+1, j), A);

            if (j > 1) build(id(i, j), id(i, j-1), A);

            if (j < m) build(id(i, j), id(i, j+1), A);

        }

    LL ans = dinic(S, T, T+1);

    printf("%lld\n", ans);

}

巴特西

Gym - 101128F Landscaping（网络流）

题意

解析

最新文章

热门文章