#### UVa 1515 – Pool construction [最小割建模]

EK算法：

```#include <bits/stdc++.h>
using namespace std;

const int maxn = 55, inf = 0x3f3f3f3f;
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int w, h, d, f, b, st, ed, cost;
char mat[maxn][maxn];

struct Edge {
int from, to, cap, flow;
Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {}
};
struct EdmondsKarp{
vector<Edge> edges;
vector<int> G[maxn*maxn];
int a[maxn*maxn], p[maxn*maxn];

void init(int n) {
for(int i = 0; i < n; ++i)
G[i].clear();
edges.clear();
}
void addEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
int m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
int maxFlow(int s, int t) {
int flow = 0;
while(true) {
memset(a, 0, sizeof(a));
queue<int> qu;
qu.push(s); a[s] = inf;
while(!qu.empty()) {
int x = qu.front(); qu.pop();
for(unsigned i = 0; i < G[x].size(); ++i) {
Edge & e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow) {
p[e.to] = G[x][i];
a[e.to] = min(a[x], e.cap - e.flow);
qu.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u = t; u != s; u = edges[p[u]].from) {
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
}EK;

inline bool in(int x, int y) {
return x >= 0 && y >= 0 && x < h && y < w;
}
inline bool inborder(int x, int y) {
return x == 0 || y == 0 || x == h - 1 || y == w - 1;
}

void build() {
EK.init(maxn*maxn);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if(mat[i][j] == '#') {
if(i) {
}
if(j) {
}
}
}
}

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d", &w, &h, &d, &f, &b);
for(int i = 0; i < h; ++i)
scanf("%s", mat[i]);
cost = 0, st = h*w, ed = h*w+1;
for(int i = 0; i < h; ++i)
for(int j = 0; j < w; ++j)
if(inborder(i, j) && mat[i][j] == '.') {
mat[i][j] = '#';
cost += f;
}
// printf("%d---\n", cost);
build();
printf("%d\n", cost + EK.maxFlow(st, ed));
}
return 0;
}
```

ISAP算法：

```#include <bits/stdc++.h>
using namespace std;

const int maxn = 55, inf = 0x3f3f3f3f;
int w, h, d, f, b, st, ed, cost;
char mat[maxn][maxn];

struct Edge{
int u, v, cap, flow;
Edge(){}
Edge(int u, int v, int cap, int flow) : u(u), v(v), cap(cap), flow(flow){}
};
struct ISAP {
int n, s, t;
int num[maxn*maxn], cur[maxn*maxn], d[maxn*maxn], p[maxn*maxn];
vector<int> G[maxn*maxn];
vector<Edge> edges;
void add(int u, int v, int cap){
edges.push_back(Edge(u, v, cap, 0));
edges.push_back(Edge(v, u, 0, 0));
int m = edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
void init(int n){
this -> n = n;
for(int i = 0; i < n; i++)
G[i].clear();
edges.clear();
}
void bfs(){
for(int i = 0; i < n; i++) d[i] = inf;
d[t] = 0;
queue<int> Q;
Q.push(t);
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(int i = 0; i < G[x].size(); i++){
Edge &e = edges[G[x][i]];
if(e.cap > 0 || d[e.v] <= d[x] + 1) continue;
d[e.v] = d[x] + 1;
Q.push(e.v);
}
}
}
int augment(){
int x = t, a = inf;
while(x != s){
Edge &e = edges[p[x]];
a = min(a, e.cap - e.flow);
x = e.u;
}
x = t;
while(x != s){
edges[p[x]].flow += a;
edges[p[x]^1].flow -= a;
x = edges[p[x]].u;
}
return a;
}
int maxflow(int s, int t){
this -> s = s;
this -> t = t;
memset(cur, 0, sizeof(cur));
memset(num, 0, sizeof(num));
bfs();
for(int i = 0; i < n; i++) if(d[i] != inf) num[d[i]]++;
int x = s, flow = 0;
while(d[s] < n){
if(x == t){
flow += augment();
x = s;
}
int ok = 0;
for(int i = cur[x]; i < G[x].size(); i++){
Edge &e = edges[G[x][i]];
if(e.cap > e.flow && d[e.v] + 1 == d[x]){
ok = 1;
cur[x] = i;
p[e.v] = G[x][i];
x = e.v;
break;
}
}
if(!ok){
int m = n - 1;
for(int i = 0; i < G[x].size(); i++){
Edge &e = edges[G[x][i]];
if(e.cap > e.flow) m = min(m, d[e.v]);
}
if(--num[d[x]] == 0) break;
++num[d[x] = m + 1];
cur[x] = 0;
if(x != s) x = edges[p[x]].u;
}
}
return flow;
}
}g;

inline bool in(int x, int y) {
return x >= 0 && y >= 0 && x < h && y < w;
}
inline bool inborder(int x, int y) {
return x == 0 || y == 0 || x == h - 1 || y == w - 1;
}

void build() {
g.init(ed+1);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if(mat[i][j] == '#') {
if(i) {
}
if(j) {
}
}
}
}

int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d", &w, &h, &d, &f, &b);
for(int i = 0; i < h; ++i)
scanf("%s", mat[i]);
cost = 0, st = h*w, ed = h*w+1;
for(int i = 0; i < h; ++i)
for(int j = 0; j < w; ++j)
if(inborder(i, j) && mat[i][j] == '.') {
mat[i][j] = '#';
cost += f;
}
// printf("%d---\n", cost);
build();
printf("%d\n", cost + g.maxflow(st, ed));
}
return 0;
}
```