记录编号	351381	评测结果	TATWTTTTTT
题目名称	2550.冰桥，升起来了！	最终得分	10
用户昵称	Tabing010102	是否通过	未通过
代码语言	C++	运行时间	8.027 s
提交时间	2016-11-16 15:05:56	内存使用	1.53 MiB

#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 40000+10;
FILE *fin, *fout;
int nA, nB, K, valA[maxn], valB[maxn];
struct Bridge {
	int from, to;
	Bridge(int a, int b) { from=a; to=b; }
};
vector<Bridge> bridges;//其中B侧的编号为原始编号
vector<int> brA[maxn];
vector<int> brB[maxn];
void AddBridge(int u, int v) {
	bridges.push_back(Bridge(u, v));
	bridges.push_back(Bridge(v, u));
	int m = bridges.size();
	brA[u].push_back(m-2);
	brB[u].push_back(m-1);
}
int ans=0;
inline int max(int a, int b) { return a<b?b:a; }
vector<Bridge> cnt_bridges;//其中B侧编号已经加maxn
vector<Bridge>::iterator it;
bool isx(int id, int w1, int w2) {
	if(id == 0) {//A侧
		Bridge x = bridges[brA[w1][w2]];
		x.to += maxn;
		for(it = cnt_bridges.begin(); it != cnt_bridges.end(); it++) {
			if(x.from<it->from && x.to>it->to) return true;
			if(x.from>it->from && x.to<it->to) return true;
		}
		return false;
	} else {//B侧
		Bridge x = bridges[brB[w1][w2]];
		x.from += maxn;
		for(it = cnt_bridges.begin(); it != cnt_bridges.end(); it++) {
			if(x.to<it->from && x.from>it->to) return true;
			if(x.to>it->from && x.from<it->to) return true;
		}
		return false;
	}
}
void dfs(int now, int cnt) {
	if(now <= maxn) {//A侧
		bool moved = false;
		for(int i = 0; i < brA[now].size(); i++) {
			if(isx(0, now, i)) continue;
			moved = true;
			Bridge &x = bridges[brA[now][i]];
			cnt_bridges.push_back(Bridge(now, x.to+maxn));
			dfs(x.to+maxn, cnt+valA[now]);
			cnt_bridges.pop_back();
		}
		if(!moved) ans = max(ans, cnt+valA[now]);
	} else {//B侧
		now -= maxn;
		bool moved = false;
		for(int i = 0; i < brB[now].size(); i++) {
			if(isx(1, now, i)) continue;
			moved = true;
			Bridge &x = bridges[brB[now][i]];
			cnt_bridges.push_back(Bridge(x.to, now+maxn));
			dfs(x.to, cnt+valB[now]);
			cnt_bridges.pop_back();
		}
		if(!moved) ans = max(ans, cnt+valB[now]);
	}
}
int main() {
	fin = fopen("meibridge.in", "r");
	fout = fopen("meibridge.out", "w");
	fscanf(fin, "%d%d%d", &nA, &nB, &K);
	for(int i = 1; i <= nA; i++) fscanf(fin, "%d", &valA[i]);
	for(int i = 1; i <= nB; i++) fscanf(fin, "%d", &valB[i]);
	for(int i = 1; i <= K; i++) {
		int u, v;
		fscanf(fin, "%d%d", &u, &v);
		AddBridge(u, v);
	}
	//dfs时1~maxn表示在A侧, maxn+1~maxn*2表示在B侧
	for(int i = 1; i <= nA; i++) dfs(i, 0);
	for(int i = 1; i <= nB; i++) dfs(i+maxn, 0);
	fprintf(fout, "%d\n", ans);
	return 0;
}