比赛 20161116 评测结果 RRRRRRRRRR
题目名称 冰桥,升起来了! 最终得分 0
用户昵称 Smile 运行时间 0.007 s
代码语言 C++ 内存使用 1.84 MiB
提交时间 2016-11-16 12:08:07
显示代码纯文本
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=40000+10;
const int INF=0x3f3f3f3f;

vector<int> ga[maxn], gb[maxn];
int va[maxn], vb[maxn];
int A, B, K;
int ha[maxn], hb[maxn];
int ans;

// flag==1 biao shi A;
int dfs(int flag, int MAX_A, int MAX_B, int u) {
	if(flag) {
		if(ha[u]) return ha[u];
		int cnt=0;
		for(int i=0; i<(int)ga[u].size(); i++) {
			if(ga[u][i]<=MAX_B) continue;
			cnt=max(cnt, va[u]+dfs(0, MAX_A, ga[u][i], ga[u][i]));
		}
		return ha[u]=cnt;
	}
	else {
		if(hb[u]) return hb[u];
		int cnt=0;
		for(int i=0; i<(int)gb[u].size(); i++) {
			if(gb[u][i]<=MAX_A) continue;
			cnt=max(cnt, vb[u]+dfs(1, gb[u][i], MAX_B, gb[u][i]));
		}
		return hb[u]=cnt;
	}
}

void init() {
	scanf("%d%d%d", &A, &B, &K);
	for(int i=1; i<=A; i++) scanf("%d", &va[i]);
	for(int i=1; i<=B; i++) scanf("%d", &vb[i]);
	for(int i=1; i<=K; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		ga[x].push_back(y);
		gb[y].push_back(x);
	}
	for(int i=1; i<=A; i++) ans=max(ans, dfs(1, 0, 0, i));
	for(int i=1; i<=B; i++) ans=max(ans, dfs(0, 0, 0, i));
	printf("%d\n", ans);
}

int main() {
	freopen("meibridge.in", "r", stdin);
	freopen("meibridge.out", "w", stdout);
	init();
	return 0;
}