POJ 2195 Going Home http://poj.org/problem?id=2195 最小费用最大流

poj2195.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

#define maxn 2110
#define maxm 2000001
const int inf = 0x3f3f3f3f;

struct Nod {
	int b, nxt;
	int cap, cst;
	void init(int b, int nxt, int cap,int cst) {
		this->b = b;
		this->nxt = nxt;
		this->cap = cap;
		this->cst = cst;
	}
};
struct MinCost {
	int E[maxn];		int n;
	Nod buf[maxm*2];	int len;
	
	int p[maxn];
	void init(int n) {
		this->n = n;
		memset(E, 255, sizeof(E));
		len = 0;
	}
	void addCap(int a, int b, int cap, int cst) {
		buf[len].init(b, E[a], cap, cst);	E[a] = len ++;
		buf[len].init(a, E[b], 0,  -cst);	E[b] = len ++;
	}
	bool spfa(int source, int sink) {
		static queue<int> q;
		static int d[maxn];
		memset(d,  63, sizeof(d));
		memset(p, 255, sizeof(p));
		
		d[source] = 0;
		q.push(source);
		int u, v;
		while(!q.empty()) {
			u = q.front();
			q.pop();
			for(int i = E[u]; i != -1; i = buf[i].nxt) {
				v = buf[i].b;
				if(buf[i].cap>0 && d[u]+buf[i].cst<d[v]) {
					d[v] = d[u]+buf[i].cst;
					p[v] = i;
					q.push(v);
				}
			}
		}
		return d[sink] != inf;
	}
	int solve(int source, int sink) {
		int minCost = 0,maxFlow = 0;//需要maxFlow的话,想办法返回
		while(spfa(source, sink)) {
			int neck = inf;
			for(int t=p[sink]; t != -1; t = p[ buf[t^1].b ])//buf[t^1].b是父节点
				neck = min(neck, buf[t].cap);
			maxFlow += neck;
			for(int t = p[sink]; t != -1; t = p[ buf[t^1].b ]) {
				buf[t].cap -= neck;
				buf[t^1].cap += neck;
				minCost += buf[t].cst * neck;
			}
		}
		//printf("%d\n", maxFlow);
		return minCost;
	}
} mf;

struct Point {
	int x, y;
	Point() {}
	Point(int xx, int yy) {
		x = xx; y = yy;
	}
};
Point x[111], y[111];

int n, m;
char ch[111][111];

void work() {
	int a = 0, b = 0;
	for (int i = 0; i < n; i++) {
		scanf("%s", ch[i]);
		for (int j = 0; j < m; j++) {
			if (ch[i][j] == 'H')
				x[a++] = Point(i, j);
			else if (ch[i][j] == 'm')
				y[b++] = Point(i, j);
		}
	}
	int s = 0, t = a + b + 1;
	mf.init(t);
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			int len = abs(x[i].x - y[j].x) 
				+ abs(x[i].y - y[j].y);
			mf.addCap(i+1, j+a+1, 1, len);
		}
	}
	for (int i = 0; i < a; i++)
		mf.addCap(s, i+1, 1, 0);
	for (int i = 0; i < b; i++)
		mf.addCap(i+a+1, t, 1, 0);
	printf("%d\n", mf.solve(s, t));
}

int main() {
	while (scanf("%d %d", &n, &m) != EOF) {
		if (n == 0 && m == 0) break;
		work();
	}
	return 0;
}