记录编号	338780	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2003][POJ2125]有向图破坏	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2016-11-05 15:23:40	内存使用	0.40 MiB

// 原图上拆点, 一个点拆成两个, 原图中的边(i, j)建成(i, j'), 容量为inf
// 超级源点到左半部分建边的容量为w-, 右半部分到超级汇点建边, 容量为w+
// 最大流

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxnode = 100 * 2 + 2 + 100, maxedge = 5000 + 100 * 2 + 100, inf = 0x3f3f3f3f;
int n, m, s, t;
struct Edge
{
	int to, cap, next;
	inline Edge() { to = cap = next = 0; }
};

namespace MaxFlow
{
	Edge edges[maxedge << 1];
	int head[maxnode] = {0}, tot = 1;
	int dis[maxnode] = {0}, cur[maxnode] = {0};
	bool vis[maxnode] = {0};
	inline void AddEdge(const int& from, const int& to, const int& cap)
	{
		edges[++tot].to = to;
		edges[tot].cap = cap;
		edges[tot].next = head[from];
		head[from] = tot;
	}
	inline bool BFS()
	{
		queue <int> Q;
		memset(vis, 0, sizeof vis);
		memset(dis, 0, sizeof dis);
		vis[s] = 1; dis[s] = 0;
		Q.push(s);
		while (!Q.empty()) {
			int front = Q.front(); Q.pop();
			for (int i = head[front]; i; i = edges[i].next) {
				int to = edges[i].to, cap = edges[i].cap;
				if (!vis[to] && cap) {
					vis[to] = 1; dis[to] = dis[front] + 1;
					Q.push(to);
				}
			}
		}
		return vis[t];
	}
	int DFS(const int& a, int minn)
	{
		if (a == t) return minn;
		int ret = 0;
		for (int& i = cur[a]; i; i = edges[i].next) {
			if (dis[edges[i].to] == dis[a] + 1 && edges[i].cap) {
				int x = DFS(edges[i].to, min(minn, edges[i].cap));
				ret += x; minn -= x;
				edges[i].cap -= x; edges[i ^ 1].cap += x;
				if (minn == 0) break;
			}
		}
		return ret;
	}
	inline int Work()
	{
		int ret = 0;
		while (BFS()) {
			for (int i = 1; i <= t; ++i)
				cur[i] = head[i];
			ret += DFS(s, inf);
		}
		return ret;
	}
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("destroyingthegraph.in", "r", stdin);
	freopen("destroyingthegraph.out", "w", stdout);
#endif

	int w, from, to;
	scanf("%d%d", &n, &m);
	s = 2 * n + 1; t = 2 * n + 2;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &w);
		MaxFlow::AddEdge(i + n, t, w);
		MaxFlow::AddEdge(t, i + n, 0);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &w);
		MaxFlow::AddEdge(s, i, w);
		MaxFlow::AddEdge(i, s, 0);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &from, &to);
		MaxFlow::AddEdge(from, to + n, inf);
		MaxFlow::AddEdge(to + n, from, 0);
	}

	printf("%d\n", MaxFlow::Work());

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}