记录编号	605005	评测结果	AAAAAA
题目名称	752.[BJOI2006] 狼抓兔子	最终得分	100
用户昵称	OTTF	是否通过	通过
代码语言	C++	运行时间	1.004 s
提交时间	2025-08-13 12:33:30	内存使用	11.28 MiB

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

template <typename PointT, typename EdgeT>
class GraphWithVector {
	private:
	PointT n;
	vector<vector<pair<PointT, EdgeT>>> graph;

	public:

	GraphWithVector (PointT n = 1e5);
	PointT getN () {return n;}
	void add (PointT u, PointT v, EdgeT w = 1);
	void addBoth (PointT u, PointT v, EdgeT w = 1);
	auto& operator [] (const PointT i) {
		return graph[i];
	}
};

template <typename PointT, typename EdgeT>
GraphWithVector<PointT, EdgeT>::GraphWithVector (PointT n) : n (n) {
	graph.resize(n);
}

template <typename PointT, typename EdgeT>
void GraphWithVector<PointT, EdgeT>::add (PointT u, PointT v, EdgeT w) {
	graph[u].emplace_back(v, w);
}

template <typename PointT, typename EdgeT>
void GraphWithVector<PointT, EdgeT>::addBoth (PointT u, PointT v, EdgeT w) {
	add (u, v, w);
	add (v, u, w);
}

template <typename PointT, typename EdgeT>
class NetworkFlow {
	private:
	PointT n;
	GraphWithVector<PointT, pair<EdgeT, PointT>> nf;

	public:

	NetworkFlow (PointT n = 1e5) : n (n), nf (n) {}
	PointT getN () {return n;}
	void add (PointT u, PointT v, EdgeT w = 1);
	auto& operator [] (const PointT i) {
		return nf[i];
	}
};

template <typename PointT, typename EdgeT>
void NetworkFlow<PointT, EdgeT>::add (PointT u, PointT v, EdgeT w) {
	nf.add(u, v, make_pair (w, nf[v].size()));
	nf.add(v, u, make_pair (w, nf[u].size() - 1));
}

template <typename PointT, typename EdgeT, typename GraphT>
class Dinic {
	private:

	GraphT& graph;
	PointT B;
	PointT E;
	vector<int> dep;
	vector<int> cur;
	EdgeT res;

	bool bfs ();
	EdgeT dfs (PointT now, EdgeT limit);

	public:

	Dinic (GraphT &graphin) : graph (graphin) {
		dep.resize(graph.getN() + 2);
		cur.resize(graph.getN() + 2);
	}
	EdgeT dinic (PointT b, PointT e);
};

template <typename PointT, typename EdgeT, typename GraphT>
bool Dinic<PointT, EdgeT, GraphT>::bfs () {
	fill (dep.begin(), dep.end(), -1);
	fill (cur.begin(), cur.end(), 0);
	
	queue<PointT> q;
	q.push(B);
	dep[B] = 0;
	
	while (!q.empty()) {
		PointT u = q.front();
		q.pop();
		
		for (auto [v, ww] : graph[u]) {
			auto [w, another] = ww;
			if (dep[v] == -1 && w != 0) {
				dep[v] = dep[u] + 1;
				q.push(v);
			}
		}
	}
	
	return (dep[E] != -1);
}

template <typename PointT, typename EdgeT, typename GraphT>
EdgeT Dinic<PointT, EdgeT, GraphT>::dfs (PointT now, EdgeT limit) {
	if (now == E) {
		return limit;
	}
	
	for (int i = cur[now]; i < graph[now].size(); i++) {
		cur[now] = i;

		PointT u = now;
		auto [v, ww] = graph[u][i];
		auto [w, another] = ww;
		
		if (dep[u] + 1 == dep[v] && graph[u][i].second.first != 0) {
			EdgeT t = dfs (v, min (w, limit));
			
			if (t) {
				graph[u][i].second.first -= t;
				graph[v][another].second.first += t;
				return t;
			}
			else {
				dep[v] = -1;
			}
		}
	}
	
	return 0;
}

template <typename PointT, typename EdgeT, typename GraphT>
EdgeT Dinic<PointT, EdgeT, GraphT>::dinic (PointT b, PointT e) {

	res = 0;
	B = b;
	E = e;

	EdgeT flow = 0;
	while (bfs ()) {
		while (flow = dfs (B, 1e9)) {
			res += flow;
		}
	}
	
	return res;
}

int n;
int m;

inline int cal (int x, int y) {
	return (x - 1) * m + y;
}

int main () {
	
	cin >> n >> m;
	NetworkFlow<int, int> nf(n * m + 2);
	int w;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < m; j++) {
			cin >> w;
			nf.add(cal (i, j), cal (i, j + 1), w);
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> w;
			nf.add(cal (i, j), cal (i + 1, j), w);
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			cin >> w;
			nf.add(cal (i, j), cal (i + 1, j + 1), w);
		}
	}

	Dinic<int, int, NetworkFlow<int, int>> dinic(nf);

	cout << dinic.dinic(cal(1, 1), cal (n, m)) << endl;
	
	return 0;
}