最小费用流的水题
我们可以以每一个格点为节点建图,也可以根据曼哈顿距离建图。都无所谓。
这题如果根据曼哈顿距离的话,其实还可以用KM算法去做。
这里给出费用流的dijstra写法:
#include<iostream> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> pii; const int inf = 1e9; const int max_n = 1e4 + 100; const int max_m = 4 * max_n; struct edge { int to, cap, rev, cost, next; }E[max_m * 4]; int head[max_n]; int cnt = 1; void add(int from, int to, int cap, int cost) { E[cnt].to = to;E[cnt].cap = cap; E[cnt].cost = cost;E[cnt].rev = cnt + 1; E[cnt].next = head[from];head[from] = cnt++; E[cnt].to = from;E[cnt].cap = 0; E[cnt].cost = -cost;E[cnt].rev = cnt - 1; E[cnt].next = head[to];head[to] = cnt++; } int dist[max_n]; pii fa[max_n]; int h[max_n]; bool dijstra(int s, int t) { fill(dist, dist + max_n, inf); priority_queue<pii, vector<pii>, greater<pii> > que; dist[s] = 0;que.push(make_pair(dist[s], s)); while (!que.empty()) { pii p = que.top();que.pop(); int u = p.second;int d = p.first; if (d > dist[u])continue; for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (e.cap > 0 && dist[e.to] > dist[u] + e.cost + h[u] - h[e.to]) { dist[e.to] = dist[u] + e.cost + h[u] - h[e.to]; fa[e.to] = make_pair(u, i); que.push(make_pair(dist[e.to], e.to)); } } }for (int i = 0;i < max_n;++i)h[i] = min(dist[i] + h[i], inf); return dist[t] != inf; } int matchpath(int s, int t, int& f) { int d = f; for (int cur = t;cur != s;cur = fa[cur].first) { edge& e = E[fa[cur].second]; d = min(d, e.cap); }for (int cur = t;cur != s;cur = fa[cur].first) { edge& e = E[fa[cur].second]; e.cap -= d;E[e.rev].cap += d; }f -= d; return d*h[t]; } int mcf(int s, int t, int f) { fill(h, h + max_n, 0); int res = 0;int cost = 0; while (f > 0 && dijstra(s, t)) { cost = matchpath(s, t, f); res += cost; }return res; } char grid[max_n][max_n]; int N, M; int get_id(int x,int y) { return (x - 1) * M + y; } int main() { ios::sync_with_stdio(0); while (cin >> N >> M) { if (N == 0 && M == 0)break; fill(head, head + max_n, 0);cnt = 1; for (int i = 1;i <= N;++i)for (int j = 1;j <= M;++j)cin >> grid[i][j]; int start = N * M + 1;int ed = start + 1; for (int i = 1;i <= N;++i) { for (int j = 1;j <= M;++j) { if (i > 1)add(get_id(i, j), get_id(i - 1, j), inf, 1); if (i < N)add(get_id(i, j), get_id(i + 1, j), inf, 1); if (j > 1)add(get_id(i, j), get_id(i, j - 1), inf, 1); if (j < N)add(get_id(i, j), get_id(i, j + 1), inf, 1); if (grid[i][j] == 'H')add(get_id(i, j), ed, 1, 0); else if (grid[i][j] == 'm')add(start, get_id(i, j), 1, 0); } }cout << mcf(start, ed, inf) << endl; } }