记录编号	569728	评测结果	AAAAAAAAAA
题目名称	[BZOJ 1458]士兵占领	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-03-16 13:08:46	内存使用	0.00 MiB

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
const int maxn = 10005;
const int maxm = 1000005;
int L[maxn],R[maxn],sum1[maxn],sum2[maxn],tot;
bool legit[maxn][maxn];
int head[maxm],ver[maxm << 1],nxt[maxm << 1],cap[maxm << 1],cur[maxm],cnt = -1;
void add(int u,int v,int t) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
	cap[cnt] = t;
	return ;
}
queue<int> q;
int level[maxn];
bool bfs(int s,int t) {
	memset(level , 0 , sizeof(level));
	q.push(s);
	level[s] = 1;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(int i = head[u];~ i;i = nxt[i]) {
			int v = ver[i];
			if(cap[i]&&!level[v]) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return level[t] > 0;
} 
int dfs(int x,int t,int maxflow) {
	if(x == t||!maxflow)return maxflow;
	int flow = 0,f;
	for(int& i = cur[x];~ i;i = nxt[i]) {
		int v = ver[i];
		if(level[v] == level[x] + 1&&(f = dfs(v , t , min(maxflow , cap[i])))) {
			if(!f) {
				level[v] = 0;
				break ;
			}
			flow += f;
			maxflow -= f;
			cap[i] -= f;
			cap[i ^ 1] += f;
			if(!maxflow)break ;
		}
	}
	return flow;
}
int Dinic(int s,int t) {
	int flow = 0;
	while(bfs(s , t)) {
		memcpy(cur , head , sizeof(head));
		flow += dfs(s , t , 0x3f3f3f3f);
	}
	return flow;
}
int main() {
	freopen("occupy.in","r",stdin);
	freopen("occupy.out","w",stdout);
	memset(head , -1 , sizeof(head));
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1;i <= n;++ i)
		for(int j = 1;j <= m;++ j)legit[i][j] = true;
	for(int i = 1;i <= n;++ i)scanf("%d",&L[i]),sum1[i] = m,tot += L[i];
	for(int i = 1;i <= m;++ i)scanf("%d",&R[i]),sum2[i] = n,tot += R[i];
	for(int i = 1;i <= k;++ i) {
		int x,y;
		scanf("%d%d",&x,&y);
		legit[x][y] = false;
		-- sum1[x];
		-- sum2[y];
	}
	bool flag = true;
	for(int i = 1;i <= n;++ i) {
		if(sum1[i] < L[i]) {
			flag = false;
			break ;
		} 
	}
	for(int i = 1;i <= m;++ i) {
		if(sum2[i] < R[i]) {
			flag = false;
			break ;
		}
	}
	if(!flag) {
		puts("JIONG!");
		return 0;
	}
	int S = n + m + 1,T = n + m + 2;
	for(int i = 1;i <= n;++ i) {
		add(S , i , L[i]);
		add(i , S , 0);
	}
	for(int i = 1;i <= m;++ i) {
		add(i + n , T , R[i]);
		add(T , i + n , 0);
	}
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= m;++ j) {
			if(legit[i][j]) {
				add(i , j + n , 1);
				add(j + n , i , 0);
			}
		}
	}
	printf("%d\n",tot - Dinic(S , T));
	return 0;
}