比赛 |
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;
}