Going Home

最小费用流的水题

我们可以以每一个格点为节点建图，也可以根据曼哈顿距离建图。都无所谓。
这题如果根据曼哈顿距离的话，其实还可以用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;
    }
}