记录编号	250727	评测结果	AAAAAAAAAA
题目名称	能量网络	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	1.354 s
提交时间	2016-04-15 19:34:17	内存使用	1.35 MiB

#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define M 1010
#define N 51000 
using namespace std;
ifstream in("energynet.in");
ofstream out("energynet.out");
int INF=(1<<28);
int A[M]={0};
int B[M]={0};
vector<int> F[M];
int n,m;
int S,T;
class edge
{
public:
	int u,v,w,cap,flow;
	void make(int a,int b,int c,int d,int e)
	{
		u=a;v=b;w=c;cap=d;flow=e;
	}
	void print()
	{
		out<<u<<' '<<v<<' '<<w<<' '<<cap<<' '<<flow<<endl;
	}
};
class Dinic
{
public:
	vector<edge> E;
	vector<int> G[N];
	bool vis[N];
	int cur[N],h[N];
	int size,flows;
	void clear(int siz)
	{
		int i;
		size=siz+1;
		E.clear();
		for(i=0;i<=size;i++)G[i].clear();
		memset(cur,0,sizeof(cur));
		memset(h,0,sizeof(h));
		memset(vis,0,sizeof(vis));
	}
	void add(int u,int v,int cap)
	{
		edge e;
		e.make(u,v,0,cap,0);
		//e.print();
		E.push_back(e);
		e.make(v,u,0,0,0);
		E.push_back(e);
		int o=E.size();
		G[u].push_back(o-2);
		G[v].push_back(o-1);
	}
	bool DinicBFS(int s,int t)
	{
		int i,u,v;
		queue<int> q;
		memset(vis,0,sizeof(vis));
		memset(h,0,sizeof(h));
		q.push(s);
		vis[s]=1;
		while(!q.empty())
		{
			u=q.front();
			q.pop();
			for(i=0;i<G[u].size();i++)
			{
				edge e=E[G[u][i]];
				v=e.v;
				if(!vis[v]&&e.cap>e.flow)
				{
					vis[v]=1;
					h[v]=h[u]+1;
					q.push(v);
				}
			}
		}
		return vis[t];
	}
	int DinicDFS(int u,int a,int t)
	{
		if(u==t||a<=0)return a;
		int flow=0,d,v;
		for(int &i=cur[u];i<G[u].size();i++)
		{
			edge &e=E[G[u][i]];
			v=e.v;
			if(h[v]==h[u]+1&&e.cap>e.flow)
			{
				d=DinicDFS(v,min(a,e.cap-e.flow),t);
				e.flow+=d;
				E[G[u][i]^1].flow-=d;
				flow+=d;
				a-=d;
			}
			if(a<=0)break;
		}
		return flow;
	}
	int maxflow(int s,int t)
	{
		int flow=0,temp;
		while(DinicBFS(s,t))
		{
			memset(cur,0,sizeof(cur));
			temp=DinicDFS(s,INF,t);
			flow+=temp;
		}
		flows=flow;
		return flow;
	}
}D;
bool com(int a,int b)
{
	return A[a]>A[b];
}
void read()
{
	int i,u,v;
	in>>n>>m;
    for(i=1;i<=n;i++)in>>A[i];
	for(i=1;i<=n;i++)in>>B[i];
	for(i=1;i<=m;i++)
	{
		in>>u>>v;
		F[u].push_back(v);
	}
}
void buildgraph()
{
	int i,j,v,col;
	S=0;col=n;
	T=m+100;
	D.clear(T);
	for(i=1;i<=n;i++)
	{
		sort(F[i].begin(),F[i].end(),com);
		D.add(S,i,B[i]);
		for(j=0;j<F[i].size();j++)
		{
			v=F[i][j];
			col++;
			D.add(v,col,INF);
			if(j!=F[i].size()-1)D.add(col,T,A[v]-A[F[i][j+1]]);
			else D.add(col,T,A[v]);
			if(j)D.add(col-1,col,INF);
		}
	}
}
void work()
{
	int ans;
	ans=D.maxflow(S,T);
	out<<ans<<endl;
}
int main()
{
	read();
	buildgraph();
	work();
	return 0;
}