记录编号	538002	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2003][POJ2125]有向图破坏	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2019-07-20 15:36:52	内存使用	14.51 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 1e9
const int maxn=750;
struct Edge{
	int next,to,flow,cap;
}e[5500*10];
int len,head[maxn],cur[maxn];
void Insert(int x,int y,int z){ 
	len++;e[len].to=y;e[len].next=head[x];e[len].cap=z;head[x]=len;
}
void Add_edge(int x,int y,int flow){
	Insert(x,y,flow);Insert(y,x,0);
}
int S,T;
int deep[maxn];
int q[maxn],Head,Tail;
bool Bfs(){
	Head=Tail=0;q[Tail++]=S;
	memset(deep,-1,sizeof(deep));deep[S]=0;
	while(Head^Tail){
		int k=q[Head++];
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(deep[j]<0 && e[i].cap>e[i].flow){
				deep[j]=deep[k]+1;
				q[Tail++]=j; 
			}
		}
	}
	return deep[T]>=0;
}
#define ex(x) ( (x&1) ? (x+1) : (x-1) )
int Dfs(int x,int flow){
	if(x==T || flow==0) return flow;
	int tot=0;
	for(int &i=cur[x];i;i=e[i].next){
		int j=e[i].to;
		if(e[i].cap>e[i].flow && deep[j]==deep[x]+1){
			int dd=Dfs(j,min(flow,e[i].cap-e[i].flow));
			e[i].flow+=dd;e[ex(i)].flow-=dd;
			tot+=dd;flow-=dd;
			if(!flow) break;
		}
	}
	return tot;
}
int ansflow;
void Maxflow(){
	ansflow=0;
	while(Bfs()){
		memcpy(cur,head,sizeof(head));
		ansflow+=Dfs(S,Inf);
	}
} 
int n,m;
void Init();
int main(){
	freopen("destroyingthegraph.in","r",stdin);
	freopen("destroyingthegraph.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	S=2*n+1;T=S+1;
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		Add_edge(i+n,T,x);
	}
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		Add_edge(S,i,x);
	}
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		Add_edge(x,y+n,Inf);
	}
	Maxflow();
	printf("%d\n",ansflow);
}