这道题要分隔草和洞， 然后刘汝佳就想到了“割”（不知道他怎么想的， 反正我没想到）
然后就按照这个思路走， 网络流建模然后求最大流最小割。
分成两部分， S和草连， 洞和T连
外围的草和S连一条无穷大的弧， 表示不能割， 若原来是洞就改成草然后加上花费。
然后非外围的草和S连一条容量为把草变成洞花费的弧， T同理。
然后相邻的格子之间连容量为围栏的弧。
最后是要把草和洞隔开， 所以求最小割就好了。
ps：这个建模好牛逼……
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 3123;
struct Edge
{int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> g[MAXN];
int h[MAXN], cur[MAXN];
int n, m, D, F, B, s = 0, t = 1;
int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
char map[60][60];void AddEdge(int from, int to, int cap)
{edges.push_back(Edge{from, to, cap, 0});edges.push_back(Edge{to, from, 0, 0});g[from].push_back(edges.size() - 2);g[to].push_back(edges.size() - 1);
}bool bfs()
{queue<int> q;q.push(s);memset(h, 0, sizeof(h));h[s] = 1;while(!q.empty()){int x = q.front(); q.pop();REP(i, 0, g[x].size()){Edge& e = edges[g[x][i]];if(e.cap > e.flow && !h[e.to]){h[e.to] = h[x] + 1;q.push(e.to);}}}return h[t];
}int dfs(int x, int a)
{if(x == t || a == 0) return a;int flow = 0, f;for(int& i = cur[x]; i < g[x].size(); i++){Edge& e = edges[g[x][i]];if(h[x] + 1 == h[e.to] && (f = dfs(e.to, min(e.cap - e.flow, a))) > 0){e.flow += f;edges[g[x][i] ^ 1].flow -= f;flow += f;if((a -= f) == 0) break;} }return flow;
}int maxflow()
{int flow = 0;while(bfs()) memset(cur, 0, sizeof(cur)), flow += dfs(s, 1e9);return flow;
}inline int ID(int x, int y)
{return x * m + y + 2;
}int main()
{int T;scanf("%d", &T);while(T--){scanf("%d%d%d%d%d", &m, &n, &D, &F, &B);REP(i, 0, MAXN) g[i].clear();edges.clear();int ans = 0;REP(i, 0, n) scanf("%s", map[i]);REP(i, 0, n)REP(j, 0, m){if(i == 0 || j == 0 || i == n - 1 || j == m - 1){if(map[i][j] == '.') ans += F;AddEdge(s, ID(i, j), 1e9);}else{if(map[i][j] == '#') AddEdge(s, ID(i, j), D);else AddEdge(ID(i, j), t, F);}REP(k, 0, 4){int x = i + dir[k][0], y = j + dir[k][1];if(0 <= x && x < n && 0 <= y && y < m) AddEdge(ID(i, j), ID(x, y), B);}}printf("%d\n", ans + maxflow());}return 0;
}