记录编号	251022	评测结果	AAAAAAAAAA
题目名称	能量网络	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	0.619 s
提交时间	2016-04-16 17:31:22	内存使用	4.79 MiB

/*
Problem:Energynet;
Language:c++;
by dydxh;
Date:2016.04.16;
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<ctime>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=1005;
const int maxm=50005;
typedef pair<int,int> Pii;
int n,m,Len=1,Cnt,Super_s,Super_e;
int A[maxn],B[maxn],Linkk[maxn+maxm];
Pii E[maxm];
struct edge{
	int y,next,v;
}e[(maxm+maxn)*6];
inline int read(){
	int x=0;bool flag=false;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-') flag=true;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
void Insert(int a,int b,int c){
	e[++Len].next=Linkk[a],Linkk[a]=Len,e[Len].y=b,e[Len].v=c;
	e[++Len].next=Linkk[b],Linkk[b]=Len,e[Len].y=a,e[Len].v=0;
	//printf("%d->%d %d\n",a,b,c);
}
bool mycmp(Pii a,Pii b){
	return ((a.first<b.first) || a.first==b.first && A[a.second]<A[b.second]);
}
void Initialize(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) A[i]=read();
	for(int i=1;i<=n;i++) B[i]=read();
	for(int i=1;i<=m;i++) E[i].first=read(),E[i].second=read();
	sort(E+1,E+1+m,mycmp);
	int Tot=0;
	for(int i=1;i<=m;i++){
		if(E[i].first==E[i-1].first && E[i].second==E[i-1].second) continue;
		E[++Tot]=E[i];
	}
	m=Tot;
}
void Build_Graph(){
	Super_s=0,Super_e=n+1,Cnt=n+1;
	for(int i=1,Last=1;i<=m;i=Last+1,Last=i){
		while(Last<m && E[Last].first==E[Last+1].first) Last++;
		for(int j=i;j<=Last;j++){
			++Cnt;
			if(j!=i){
				Insert(Cnt-1,Cnt,oo);
				Insert(Super_s,Cnt,A[E[j].second]-A[E[j-1].second]);
			}
			else Insert(Super_s,Cnt,A[E[i].second]);
			Insert(Cnt,E[j].second,oo);
		}
	}
	for(int i=1;i<=n;i++) Insert(i,Super_e,B[i]);
}
int Head,Tail;
int Q[maxn+maxm],Level[maxn+maxm];
bool Make_Level(){
	memset(Level,-1,sizeof(Level));
	Level[Super_s]=0,Q[Tail=1]=Super_s,Head=0;
	while(Head<Tail){
		int Tn=Q[++Head];
		for(int i=Linkk[Tn];i;i=e[i].next){
			int Tmp=e[i].y;
			if(Level[Tmp]!=-1 || e[i].v==0) continue;
			Level[Tmp]=Level[Tn]+1,Q[++Tail]=Tmp;
		}
	}
	return Level[Super_e]!=-1;
}
inline int min(const int &a,const int &b){return a<b?a:b;}
int Dfs(int x,int Flow){
	if(x==Super_e) return Flow;
	int D=0,Maxx=0;
	for(int i=Linkk[x];i && Maxx<Flow;i=e[i].next){
		int Tn=e[i].y;
		if(Level[Tn]!=Level[x]+1 || e[i].v==0) continue;
		D=Dfs(Tn,min(e[i].v,Flow-Maxx));
		if(D) e[i].v-=D,e[i^1].v+=D,Maxx+=D;
	}
	if(Maxx==0) Level[x]=-1;
	return Maxx;
}
int Dinic(){
	int Final=0;
	while(Make_Level())
		Final+=Dfs(Super_s,oo);
	return Final;
}
int main(){
	//freopen("cc.in","r",stdin);
	freopen("energynet.in","r",stdin);
	freopen("energynet.out","w",stdout);
	Initialize();
	Build_Graph();
	cout<<Dinic()<<endl;
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
    return 0;
}