记录编号	277575	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 运输问题	最终得分	100
用户昵称	prefect1999	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-07-05 22:52:31	内存使用	0.33 MiB

/*
费用流：
源点向仓库连边，容量为a[i]。
仓库向零售店连边，容量为inf，费用为c[i][j]（最优方案），费用为-c[i][j]（最差方案）。
零售店向汇点连边，容量为b[i]。
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int inf = 1 << 30;
const int maxn = 500;
struct edge
{
	int from, to, cap, flow, cost;
	edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w){}
};
struct MCMF
{
	int n, m;
	vector<edge> edges;
	vector<int> G[maxn];
	int inq[maxn];
	int d[maxn];
	int p[maxn];
	int a[maxn];
	void init(int n)
	{
		this->n = n;
		for (int i = 0; i < n; ++i)
			G[i].clear();
		edges.clear();
	}
	void add_edge(int from, int to, int cap, int cost)
	{
		edges.push_back(edge(from, to, cap, 0, cost));
		edges.push_back(edge(to, from, 0, 0, -cost));
		m = edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}
	bool BellmanFord(int s, int t, int &flow, long long &cost)
	{
		for (int i = 0; i < n; ++i)
			d[i] = inf;
		memset(inq, 0, sizeof(inq));
		d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = inf;
		queue<int> Q;
		Q.push(s);
		while (!Q.empty())
		{
			int u = Q.front(); Q.pop();
			inq[u] = false;
			for (int i = 0; i < (int)G[u].size(); ++i)
			{
				edge &e = edges[G[u][i]];
				if (e.cap > e.flow && d[e.to] > d[u] + e.cost)
				{
					d[e.to] = d[u] + e.cost;
					p[e.to] = G[u][i];
					a[e.to] = min(a[u], e.cap - e.flow);
					if (!inq[e.to])
					{
						Q.push(e.to);
						inq[e.to] = true;
					}
				}
			}
		}
		if (d[t] == inf)
			return false;
		flow += a[t];
		cost += (long long)d[t] * (long long)a[t];
		for (int u = t; u != s; u = edges[p[u]].from)
		{
			edges[p[u]].flow += a[t];
			edges[p[u]^1].flow -= a[t];
		}
		return true;
	}
	int solve(int s, int t, long long &cost)
	{
		int flow = 0; cost = 0;
		while (BellmanFord(s, t, flow, cost));
		return flow;
	}
}mcmf;
int A[maxn], B[maxn];
int main()
{
	freopen("tran.in", "r", stdin);
	freopen("tran.out", "w", stdout);
	int n, m;
	scanf("%d %d", &m, &n);
	long long cost = 0;
	const int s = n + m + 2, t = n + m + 3;
	mcmf.init(n + m + 5);
	for (int i = 0; i < m; ++i)
	{
		scanf("%d", &A[i]);
		mcmf.add_edge(s, i, A[i], 0);
	}
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &B[i]);
		mcmf.add_edge(m + i, t, B[i], 0);
	}
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int cost;
			scanf("%d", &cost);
			mcmf.add_edge(i, m + j, inf, cost);
		}
	}
	mcmf.solve(s, t, cost);
	cout << cost << endl;
	for (int i = 0; i < (int)mcmf.edges.size(); ++i)
	{
		edge &e = mcmf.edges[i];
		e.flow = 0;
		e.cost = -e.cost;
	}
	mcmf.solve(s, t, cost);
	cout << -cost << endl;	
	return 0;
}