[bzoj 1458] 士兵占领

M*M的棋盘, 一个格子至多放一个士兵, 某K个有障碍的格子不能放. 要求第i行至少放Li个, 第j列至少放Cj个, 求最少士兵数目, 或报告无解. (M,N≤100, 0≤K≤M*N) 放一个士兵, 等价于选未被禁止的一行和一列, 使该行, 该列的计数器+1 - 行, 列之间的匹配. 但这里是至少不是至多, 不能直接跑最大流. 固然可以跑一个最小可行流, 转念一想没必要绕这个弯......可以选择哪些没有障碍的格子不放士兵.

#define ROW(i) (i)
#define COL(i) ((i)+m)
#define S 0
#define T (n+m+1)

const int N = 100, inf = 1e9;
bool f[N+1][N+1];
int l[N+1], c[N+1];

namespace MaxFlow {
	const int N = 202;
	
	struct Edge {
		int u, v, c;
	};
	vector<Edge> E;
	vector<int> adj[N];

	inline void add(int u, int v, int c)
	{
		adj[u].pb(E.size());
		E.pb((Edge){u, v, c});
		adj[v].pb(E.size());
		E.pb((Edge){v, u, 0});
	}

	int level[N], cur[N], s, t, n;

	bool bfs()
	{
		queue<int> Q;
		Q.push(s);
		fill_n(level, n, -1);
		level[s] = 0;

		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			rep (i, 0, adj[u].size()) {
				Edge& e = E[adj[u][i]];
				if (e.c && level[e.v] == -1) {
					level[e.v] = level[u] + 1;
					Q.push(e.v);
				}
			}
		}

		return level[t] != -1;
	}

	int dfs(int u, int f)
	{
		if (u == t) return f;
		int res = f, d;

		for (int& i = cur[u]; i < (int)adj[u].size(); ++i) {
			Edge& e = E[adj[u][i]];
			if (level[e.v] == level[u] + 1 && e.c && (d = dfs(e.v, min(res, e.c)))) {
				e.c -= d;
				E[adj[u][i]^1].c += d;
				res -= d;
				if (!res) break;
			}
		}

		return f - res;
	}

	int max_flow(int _s, int _t, int _n)
	{
		s = _s, t = _t, n = _n;
		int f = 0;
		while (bfs()) {
			fill_n(cur, n, 0);
			f += dfs(s, inf);
		}
		return f;
	}
}

using MaxFlow::add;

int main()
{
	int m, n, k;
	scanf("%d%d%d", &m, &n, &k);
	rep (i, 1, m+1)
		scanf("%d", &l[i]);
	rep (i, 1, n+1)
		scanf("%d", &c[i]);
	rep (i, 0, k) {
		int x, y;
		scanf("%d%d", &x, &y);
		f[x][y] = true;
	}
	rep (i, 1, m+1) {
		int cnt = 0;
		rep (j, 1, n+1)
			if (!f[i][j]) {
				add(ROW(i), COL(j), 1);
				++cnt;
			}
		if (cnt < l[i]) {
			puts("JIONG!");
			return 0;
		}
		add(S, ROW(i), cnt - l[i]);
	}
	rep (i, 1, n+1) {
		int cnt = 0;
		rep (j, 1, m+1)
			cnt += !f[j][i];
		if (cnt < c[i]) {
			puts("JIONG!");
			return 0;
		}
		add(COL(i), T, cnt - c[i]);
	}

	printf("%d\n", n*m - k - MaxFlow::max_flow(S, T, n+m+2));
	return 0;
}