比赛 |
20161116 |
评测结果 |
AWWAWAWAWA |
题目名称 |
冰桥,升起来了! |
最终得分 |
50 |
用户昵称 |
Riolu |
运行时间 |
0.921 s |
代码语言 |
C++ |
内存使用 |
1.42 MiB |
提交时间 |
2016-11-16 10:44:56 |
显示代码纯文本
/*=========================================*
* Auther: Riolu
* Time: 2016.11.16
* ©Copyright 2016 Riolu. All Rights Reserved.
*=========================================*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
//#include<cmath>
#include<string>
//#include<ctime>
#include<cstring>
using namespace std;
#define v first
#define w second
typedef pair<int,int> P;
typedef long long ll;
typedef double db;
const int N =4e4+1,M=1e5+1;
int a,b,k;
int wa[N],wb[N];
//struct edge{int u,w;} e[M];
vector<P> ul[N],ur[N];
void read(){
scanf("%d%d%d",&a,&b,&k);
int i,x,y;
for(i=1;i<=a;i++)scanf("%d",&wa[i]);
for(i=1;i<=b;i++)scanf("%d",&wb[i]);
for(i=1;i<=k;i++){
//scanf("%d%d",&e[i].u,&e[i].v);
scanf("%d%d",&x,&y);
ul[x].push_back(P(y,-1));
ur[y].push_back(P(x,-1));
}
}
bool vis[N];
int ans;
int dfs(int side,int x,int dl,int dr){
//ans=max(ans,val);
int nxt,tans=0;
//cout<<side<<' '<<x<<' '<<dl<<' '<<dr<<endl;
if(side==0){
int i,l=ul[x].size();
for(i=0;i<l;i++){
nxt=ul[x][i].v;
if(nxt>dr){
if(ul[x][i].w<0)
ul[x][i].w=dfs(1,nxt,dl,nxt);
tans=max(tans,ul[x][i].w);
//cout<<x<<' '<<nxt<<' '<<ul[x][i].w<<endl;
}
}
tans+=wa[x];
}else{
int i,l=ur[x].size();
for(i=0;i<l;i++){
nxt=ur[x][i].v;
if(nxt>dl){
if(ur[x][i].w<0)
ur[x][i].w=dfs(0,nxt,nxt,dr);
tans=max(tans,ur[x][i].w);
//cout<<x<<' '<<nxt<<' '<<ur[x][i].w<<endl;
}
}
tans+=wb[x];
}
return tans;
}
int main(){
freopen("meibridge.in","r",stdin);
freopen("meibridge.out","w",stdout);
read();
for(int i=a;i>=1;i--){
ans=max(ans,dfs(0,i,i,0));
//cout<<"-----------"<<endl;
}
printf("%d\n",ans);
//cout<<ans<<endl;
fclose(stdin);fclose(stdout);
return 0;
}
/*
9
1 3 3 2 100 100 100 999 888
*/