链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4261
题意：
输入一个h行w列的字符矩阵，草地用“#”表示，洞用“.”表示。
你可以把草改成洞，每格花费为d，也可以把洞填上草，每格花费为f。
最后还需要在草和洞之间修围栏，每条边的花费为b。
整个矩阵第一行/列和最后一行/列必须都是草。
求最小花费。2≤w,h≤50，1≤d, f, b≤10000。
分析：
围栏的作用是把草和洞隔开，让人联想到了“割”这个概念。
可是“割”只是把图中的结点分成了两个部分，而本题中，草和洞都能有多个连通块。怎么办呢？
添加源点S和汇点T，与其他点相连，则所有本不连通的草地/洞就能通过源点和汇点间接连起来了。
由于草和洞可以相互转换，而且转换还需要费用，所以需要一并在“割”中体现出来。
为此，规定与S连通的都是草，与T连通的都是洞，
则S需要往所有草格子连一条容量为d的边，表示必须把这条弧切断（割的容量增加d），
这个格子才能“叛逃”到T的“阵营”，成为洞。
由于题目说明了最外圈的草不能改成洞，从S到这些草格子的边容量应为正无穷
（在这之前需要把边界上的所有洞填成草，累加出这一步所需的费用）。
同理，所有不在边界上的洞格子往T连一条弧，费用为f，
表示必须把这条弧切断（割的容量增加f），才能让这个洞变成草。
相邻两个格子u和v之间需要连两条边u->v和v->u，容量均为b，
表示如果u是草，v是洞，则需要切断弧u->v；如果v是草，u是洞，则需要切断弧v->u。
这样，用最大流算法求出最小割，就可以得到本题的最小花费。
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std; /// 结点下标从0开始，注意maxn
struct Dinic {
static const int maxn = * + ;
static const int INF = 0x3f3f3f3f;
struct Edge {
int from, to, cap, flow;
}; int n, m, s, t; // 结点数，边数（包括反向弧），源点编号和汇点编号
vector<Edge> edges; // 边表。edges[e]和edges[e^1]互为反向弧
vector<int> G[maxn]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn]; // BFS使用
int d[maxn]; // 从起点到i的距离
int cur[maxn]; // 当前弧下标 void init(int n) {
this->n = n;
edges.clear();
for(int i = ; i < n; i++) G[i].clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back((Edge){from, to, cap, });
edges.push_back((Edge){to, from, , });
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
bool BFS() {
memset(vis, , sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = ;
d[s] = ;
while(!Q.empty()) {
int x = Q.front(); Q.pop();
for(int i = ; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if(!vis[e.to] && e.cap > e.flow) { // 只考虑残量网络中的弧
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x, int a) {
if(x == t || a == ) return a;
int flow = , f;
for(int& i = cur[x]; i < G[x].size(); i++) { // 从上次考虑的弧
Edge& e = edges[G[x][i]];
if(d[x]+ == d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow))) > ) {
e.flow += f;
edges[G[x][i]^].flow -= f;
flow += f;
a -= f;
if(a == ) break;
}
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = ;
while(BFS()) {
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
vector<int> Mincut() { // 在Maxflow之后调用
vector<int> ans;
for(int i = ; i < edges.size(); i++) {
Edge& e = edges[i];
if(vis[e.from] && !vis[e.to] && e.cap > ) ans.push_back(i);
}
return ans;
}
} dc; const int INF = 0x3f3f3f3f;
const int UP = + ;
int r, c;
char site[UP][UP];
inline int id(int rr, int cc) { return rr*c+cc; } int main() {
int T, d, f, b;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d", &c, &r, &d, &f, &b);
for(int i = ; i < r; i++) scanf("%s", site[i]);
int ans = ;
for(int i = ; i < r; i++) {
if(site[i][] == '.') site[i][] = '#', ans += f;
if(site[i][c-] == '.') site[i][c-] = '#', ans += f;
}
for(int i = ; i < c; i++) {
if(site[][i] == '.') site[][i] = '#', ans += f;
if(site[r-][i] == '.') site[r-][i] = '#', ans += f;
} dc.init(r*c+);
int start = r*c, finish = r*c+;
for(int rr = ; rr < r; rr++) {
for(int cc = ; cc < c; cc++) {
if(site[rr][cc] == '#') {
int cap = (rr== || rr==r- || cc== || cc==c-) ? INF : d;
dc.AddEdge(start, id(rr,cc), cap);
} else dc.AddEdge(id(rr,cc), finish, f);
if(rr > ) dc.AddEdge(id(rr,cc), id(rr-,cc), b);
if(rr < r-) dc.AddEdge(id(rr,cc), id(rr+,cc), b);
if(cc > ) dc.AddEdge(id(rr,cc), id(rr,cc-), b);
if(cc < c-) dc.AddEdge(id(rr,cc), id(rr,cc+), b);
}
}
printf("%d\n", ans + dc.Maxflow(start, finish));
}
return ;
}