比赛 |
20161116 |
评测结果 |
WWWWWWWWWW |
题目名称 |
冰桥,升起来了! |
最终得分 |
0 |
用户昵称 |
coolkid |
运行时间 |
0.190 s |
代码语言 |
C++ |
内存使用 |
16.34 MiB |
提交时间 |
2016-11-16 11:54:38 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=300010;
struct Edge{
int from,to,nxt,dist;
int opt;
}edges[MAXN<<1];
int vis[MAXN];
int head[MAXN],cnt=0;
void addedge(int f,int t,int d,int opt){
edges[cnt].opt=opt;
edges[cnt].from=f;
edges[cnt].to=t;
edges[cnt].nxt=head[f];
edges[cnt].dist=d;
head[f]=cnt++;
}
int p1[MAXN],p2[MAXN];
int A,B,K;
int ans=0;
void init(){
cin>>A>>B>>K;
for(int i=1;i<=A;i++) scanf("%d",&p1[i]),ans+=p1[i];
for(int j=1;j<=B;j++) scanf("%d",&p2[j]),ans+=p2[j];
for(int i=1;i<=K;i++){
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y,p1[x]+p2[y],1);
addedge(y,x,p2[y]+p2[y],0);
}
}
void dfs(int u,int sum){
for(int i=head[u];~i;i=edges[i].nxt)if(!vis[i]){
int v=edges[i].to;
vis[i]=1;vis[i^1]=1;
int opt=edges[i].opt;
if(opt){
for(int j=0;j<cnt;j++) if(opt&&u<edges[j].from&&v>edges[j].to) vis[j]=vis[j^1]=1;
}else{
for(int j=0;j<cnt;j++) if(!opt&&u>edges[j].from&&v<edges[j].to) vis[j]=vis[j^1]=1;
}
dfs(v,sum+edges[i].dist);
if(opt){
for(int j=0;j<cnt;j++) if(opt&&u<edges[j].from&&v>edges[j].to) vis[j]=vis[j^1]=0;
}else{
for(int j=0;j<cnt;j++) if(!opt&&u>edges[j].from&&v<edges[j].to) vis[j]=vis[j^1]=0;
}
vis[i]=0;vis[i^1]=0;
}
}
int main(){
freopen("meibridge.in","r",stdin);
freopen("meibridge.out","w",stdout);
init();
cout<<ans<<endl;
return 0;
}