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