本文共 2696 字，大约阅读时间需要 8 分钟。
题意：n*m的地，从有高地和低地，从高地走到低地或者从低地走到高地花费a，把高地和低地互相改造一次花费b。现在要走遍每一行每一列，问最小花费
思路：超级源点连接所有低地，容量b；所有地向四周建边，容量a；高地连接超级汇点，容量b。假如sum(a) > b，那么流出b，即这个地改造；假如sum(a) < b，那么就不改造。
代码：
#include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 50 * 50 + 10;const int M = maxn * 30;const ull seed = 131;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;struct Edge{ int to, next, flow, cap;}edge[maxn * 10];int tot;int head[maxn];int gap[maxn], dep[maxn], pre[maxn], cur[maxn];void init(){ tot = 0; memset(head, -1, sizeof(head));}void addEdge(int u, int v, int w, int rw = 0){ edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = 0; edge[tot].next = head[u]; head[u] = tot++; edge[tot].to = u; edge[tot].cap = rw; edge[tot].flow = 0; edge[tot].next = head[v]; head[v] = tot++;}int sap(int start, int end, int N){ memset(gap, 0, sizeof(gap)); memset(dep, 0, sizeof(dep)); memcpy(cur, head, sizeof(head)); int u = start; pre[u] = -1; gap[u] = N; int ans = 0; while(dep[start] < N){ if(u == end){ int Min = INF; for(int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to]){ Min = min(Min, edge[i].cap - edge[i].flow); } for(int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to]){ edge[i].flow += Min; edge[i ^ 1].flow -= Min; } u = start; ans += Min; continue; } bool flag = false; int v; for(int i = cur[u]; i != -1; i = edge[i].next){ v = edge[i].to; if(edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]){ flag = true; cur[u] = pre[v] = i; break; } } if(flag){ u = v; continue; } int Min = N; for(int i = head[u]; i != -1; i = edge[i].next){ if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){ Min = dep[edge[i].to]; cur[u] = i; } } gap[dep[u]]--; if(!gap[dep[u]]) return ans; dep[u] = Min + 1; gap[dep[u]]++; if(u != start) u = edge[pre[u] ^ 1].to; } return ans;}char mp[maxn][maxn];int n, m;int getid(int x, int y){ return (x - 1) * m + y;}int to[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0};int main(){ int a, b; scanf("%d%d", &n, &m); scanf("%d%d", &a, &b); int s = n * m + 1, e = n * m + 2; init(); for(int i = 1; i <= n; i++){ scanf("%s", mp[i] + 1); for(int j = 1; j <= m; j++){ if(mp[i][j] == '.'){ addEdge(s, getid(i, j), b); } else{ addEdge(getid(i, j), e, b); } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ for(int k = 0; k < 4; k++){ int x = i + to[k][0]; int y = j + to[k][1]; if(x < 1 || y < 1 || x > n || y > m) continue; addEdge(getid(i, j), getid(x, y), a); } } } int ans = sap(s, e, n * m + 2); printf("%d\n", ans); return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/10865131.html
