学步园

题目大意：有一些仓库，一些零售店。现在零售店从仓库进货。给出每个仓库有多少货物，每个零售店需要多少货物，还有单位货物从仓库运送到零售店的价格。求满足所有零售店需求的最小费用和最大费用。

思路：最小费用最大流，最大费用最大流。避免重复，为了好写，我把解费用装到了一个结构体里。

建图方法：源向所有仓库连边，费用0，流量为仓库里的东西多少。

所有零售店向汇连边，费用0，流量为零售店需要的货物多少。

所有仓库向所有零售店连边，流量正无穷，费用为单位费用。

之后跑EK就可以了。

poj3680和poj2516都是这种键图方法的题，2516的读入和处理略恶心。。。

CODE：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 10000
#define S 0
#define T (houses + stores + 1)
#define INF 0x3f3f3f3f
using namespace std;

int houses,stores;

struct CostFlow{
	int head[MAX],total;
	int next[MAX],aim[MAX],flow[MAX],cost[MAX];

	int f[MAX],p[MAX],from[MAX];
	bool v[MAX];

	CostFlow() {
		total = 1;
	}
	void Add(int x,int y,int f,int c) {
		next[++total] = head[x];
		aim[total] = y;
		flow[total] = f;
		cost[total] = c;
		head[x] = total;
	}
	bool SPFA() {
		static queue<int> q;
		while(!q.empty())	q.pop();
		memset(f,0x3f,sizeof(f));
		memset(v,false,sizeof(v));
		memset(from,-1,sizeof(from));
		f[S] = 0;
		q.push(S);
		while(!q.empty()) {
			int x = q.front(); q.pop();
			v[x] = false;
			for(int i = head[x];i;i = next[i])  {
				if(flow[i] && f[aim[i]] > f[x] + cost[i]) {
					f[aim[i]] = f[x] + cost[i];
					if(!v[aim[i]]) {
						v[aim[i]] = true;
						q.push(aim[i]);
					}
					p[aim[i]] = i;
					from[aim[i]] = x;
				}
			}
		}
		return from[T] != -1;
	}
	int EdmondsKarp() {
		int re = 0;
		while(SPFA()) {
			int remain_flow = INF;
			for(int i = T;i != S;i = from[i])
				remain_flow = min(remain_flow,flow[p[i]]);
			for(int i = T;i != S;i = from[i]) {
				flow[p[i]] -= remain_flow;
				flow[p[i]^1] += remain_flow;
			}
			re += f[T] * remain_flow;
		}
		return re;
	}
}min_solver,max_solver;

int main()
{
	cin >> houses >> stores;
	for(int x,i = 1;i <= houses; ++i) {
		scanf("%d",&x);
		min_solver.Add(S,i,x,0);
		min_solver.Add(i,S,0,0);
		max_solver.Add(S,i,x,0);
		max_solver.Add(i,S,0,0);
	}
	for(int x,i = 1;i <= stores; ++i) {
		scanf("%d",&x);
		min_solver.Add(i + houses,T,x,0);
		min_solver.Add(T,i + houses,0,0);
		max_solver.Add(i + houses,T,x,0);
		max_solver.Add(T,i + houses,0,0);
	}
	for(int i = 1;i <= houses; ++i)
		for(int x,j = 1;j <= stores; ++j) {
			scanf("%d",&x);
			min_solver.Add(i,j + houses,INF,x);
			min_solver.Add(j + houses,i,0,-x);
			max_solver.Add(i,j + houses,INF,-x);
			max_solver.Add(j + houses,i,0,x);
		}
	cout << min_solver.EdmondsKarp() << endl << -max_solver.EdmondsKarp() << endl;
	return 0;
}