Uva1515 pool construction max flow min cut

The main idea of the topic

Give a matrix of h * w, 'ා' for grassland, '. For hole, d for hole, f for hole, b for fence between hole and edge of grassland, and find the minimum cost.

It is required that the edge of matrix must be grass.

thinking

Each element in the matrix is a node, which is divided into two sets: s set and T set. Finally, the node of s set connected with s is grassland, and the node of T set is hole.

When the edge enters the minimum cut, the node enters the T-set, that is, the grassland becomes a hole, and the edge of the edge grassland and the edge of s which has no INF capacity cannot enter the cut set.

Similarly, the node of hole and the point of t establish the edge with the capacity of f.

In the matrix, two-way capacity b edge is established between adjacent nodes. When the final adjacent nodes are in S set and T set respectively, this edge enters the cut set.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
#define rep0(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define rep_0(i, n) for (int i = n - 1; i >= 0; i--)
#define rep_1(i, n) for (int i = n; i > 0; i--)
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define mem(x, y) memset(x, y, sizeof(x))
#define MAXW 100
#define idx(x, y) ((x) * 50 + (y))
using namespace std;
typedef long long ll;
const int T = MAXW * MAXW - 1;
struct Edge
{
    int to, cap, flow, rev;
};
vector<Edge> G[MAXW * MAXW];
void addEdge(int u, int v, int cap)
{
    G[u].push_back((Edge){v, cap, 0, G[v].size()});
    G[v].push_back((Edge){u, 0, 0, G[u].size() - 1});

}

int d, f, b;
int w, h;
char g[MAXW][MAXW];
int level[MAXW * MAXW], itr[MAXW * MAXW];

void bfs()
{
    mem(level, -1);
    level[0] = 0;
    queue<int> q;
    q.push(0);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++)
        {
            Edge e = G[u][i];
            if (level[e.to] < 0 && e.cap > e.flow)
            {
                q.push(e.to);
                level[e.to] = level[u] + 1;
            }
        }
    }


}
int dfs(int u, int f)
{
    if (u == T)
        return f;

    for (int& i = itr[u]; i < G[u].size(); i++)
    {
        Edge& e = G[u][i];
        if (level[e.to] > level[u] && e.cap > e.flow)
        {
            int d = dfs(e.to, MIN(f, e.cap - e.flow));
            if (d)
            {
                e.flow += d;
                G[e.to][e.rev].flow -= d;
                return d;
            }
        }
    }
    return 0;
}
ll max_flow()
{
    ll flow = 0;

    while (true)
    {
        bfs();
        if (level[T] < 0)
            return flow;

        ll f;
        mem(itr, 0);

        while ((f = dfs(0, INF)) > 0)
        {
            flow += f;
        }
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif // ONLINE_JUDGE
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &w, &h);
        scanf("%d %d %d", &d, &f, &b);
        for (int i = 0; i < h; i++)
        {
            scanf("%s", g[i]);

        }

        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                G[i * 50 + j].clear();
        ll ans = 0;
        for (int i = 0; i < w; i++)
            if (g[0][i] == '.')
                ans += f;
        for (int i = 0; i < w; i++)
            if (g[h - 1][i] == '.')
                ans += f;
        for (int i = 1; i < h - 1; i++)
            if (g[i][0] == '.')
                ans += f;
        for (int i = 1; i < h - 1; i++)
            if (g[i][w - 1] == '.')
                ans += f;
        if (w == 2 || h == 2)
        {
            printf("%lld\n", ans);
            continue;
        }
        for (int i = 1; i < w - 1; i++)
        {
            addEdge(0, idx(0, i), INF);
            addEdge(0, idx(h - 1, i), INF);
            addEdge(idx(h - 1, i), idx(h - 2, i), b);

        }
        for (int i = 1; i < h - 1; i++)
        {
            addEdge(0, idx(i, 0), INF);
            addEdge(0, idx(i, w - 1), INF);
            addEdge(idx(i, w - 1), idx(i, w - 2), b);
        }

        for (int i = 1; i < h - 1; i++)
        {
            for (int j = 1; j < w - 1; j++)
            {
                addEdge(idx(i - 1, j), idx(i, j), b);
                addEdge(idx(i, j), idx(i - 1, j), b);
                addEdge(idx(i, j - 1), idx(i, j), b);
                addEdge(idx(i, j), idx(i, j - 1), b);
                if (g[i][j] == '#')
                {
                    addEdge(0, idx(i, j), d);

                }
                else
                {
                    addEdge(idx(i, j), T, f);

                }
            }
        }

        ans += max_flow();
        printf("%lld\n", ans);




    }




    return 0;
}

 

Posted on Sun, 09 Feb 2020 08:30:54 -0800 by Seol