这道题要分隔草和洞， 然后刘汝佳就想到了“割”（不知道他怎么想的， 反正我没想到）
然后就按照这个思路走， 网络流建模然后求最大流最小割。
分成两部分， S和草连， 洞和T连
外围的草和S连一条无穷大的弧， 表示不能割， 若原来是洞就改成草然后加上花费。
然后非外围的草和S连一条容量为把草变成洞花费的弧， T同理。
然后相邻的格子之间连容量为围栏的弧。
最后是要把草和洞隔开， 所以求最小割就好了。
ps：这个建模好牛逼……
#include#include #include #include #include #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 edges;vector 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 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; }