HDU 2426 Interesting Housing Problem http://acm.hdu.edu.cn/showproblem.php?pid=2426 最小费用最大流

hdu2426.cpp

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

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

int nn, m, e;

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);
		if (maxFlow != nn)
			return 1;
		return minCost;
	}
} mf;


void work() {
	int s = 0, t = nn + m + 1;
	mf.init(t);
	for (int i = 0; i < e; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		a++; b++;
		if (c >= 0)
			mf.addCap(a, b+nn, 1, -c);
	}
	for (int i = 1; i <= nn; i++)
		mf.addCap(s, i, 1, 0);
	for (int i = 1; i <= m; i++)
		mf.addCap(i+nn, t, 1, 0);
	printf("%d\n", -mf.solve(s, t));
}

int main() {
	int cas = 1;
	while (scanf("%d %d %d", &nn, &m, &e) != EOF) {
		printf("Case %d: ", cas++);
		work();
	}
	return 0;
}