记录编号	95038	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2003][POJ2125]有向图破坏	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.146 s
提交时间	2014-04-03 15:14:46	内存使用	0.31 MiB

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<string.h>

using namespace std;

//1<=N<=100,1<=M<=5000
const int MAXN=100+10;
const int MAXM=5000+10;
const int INF=10000*10000*5;

struct edge{
	int from,to,cap,flow;
	int cost;
};

struct min_cost_max_flow{
	vector<edge> edges;
	vector<int> G[MAXN*3];
	int n,m,s,t;
	
	void add_edge(int from,int to,int cap,int cost){
		edges.push_back((edge){from,to,cap,0,cost});
		edges.push_back((edge){to,from,0,0,-cost});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	int d[MAXN*3],path[MAXN*3];
	bool inq[MAXN*3];
	int find_p(int &c){
		queue<int> q;
		for(int i=0;i<=n;i++)d[i]=INF;
		memset(inq,0,sizeof(inq));
		d[s]=0;q.push(s);inq[s]=true;
		while(!q.empty()){
			int u=q.front();q.pop();inq[u]=false;
			for(int i=0;i<G[u].size();i++){
				edge &e=edges[G[u][i]];
				if(e.cap<=e.flow || d[e.to]<=d[u]+e.cost)continue;
				d[e.to]=d[u]+e.cost;
				path[e.to]=G[u][i];
				if(!inq[e.to]){
					q.push(e.to);
					inq[e.to]=true;
				}
			}
		}
		
		if(d[t]==INF)return 0;
		
		c=0;
		int flow=INF;
		int x=t;
		while(x!=s){
			edge &e=edges[path[x]];
			flow=min(e.cap-e.flow,flow);
			x=e.from;
		//	printf("%d ",x);
		}
	//	printf("\n");
		x=t;
		while(x!=s){
			edge &e=edges[path[x]];
			edge &ee=edges[path[x]^1];
			e.flow+=flow;
			ee.flow-=flow;
			c+=flow*e.cost;
			x=e.from;
		}
		return flow;
	}
	
	int max_flow(){
		int flow=0;
		int cost=0;
		int f,c;
		while(f=find_p(c)){
			flow+=f;
			cost+=c;
		}
		return flow;
	}
	
	void test(){
		for(int i=0;i<edges.size();i++){
			edge &e=edges[i];
			printf("from:%d to:%d cap:%d flow:%d cost:%d\n",e.from,e.to,e.cap,e.flow,e.cost);
		}
	}
}solver;

void read_build(){
	int n,m;
	scanf("%d %d",&n,&m);
	int s=0,t=2*n+1;
	for(int i=n+1;i<=2*n;i++){
		int x;scanf("%d",&x);
		solver.add_edge(i,t,x,0);
	}
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		solver.add_edge(s,i,x,0);
	}

	solver.s=s;solver.t=t;solver.n=2*n+2;
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		solver.add_edge(u,v+n,INF,0);
	}
}

void work(){
	read_build();
	int ans=solver.max_flow();
	printf("%d\n",ans);
	//solver.test();
}

void open(){
	freopen("destroyingthegraph.in","r",stdin);
	freopen("destroyingthegraph.out","w",stdout);
}

int main(){
	open();
	work();
	return 0;
}