# 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(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, 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] == '#')
{

}
else
{

}
}
}

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

}

return 0;
}
```

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