记录编号	495551	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2003][POJ2125]有向图破坏	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2018-04-21 00:32:29	内存使用	0.32 MiB

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define inf (int)1e9
using namespace std;
const int maxn=500;
struct Edge{int from,to,cap,flow;};
vector<Edge>edges;
vector<int>G[maxn];
int n,m,s,t,sum,d[maxn],cur[maxn];
bool vis[maxn];
void addedge(int from,int to,int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int h=edges.size();
	G[from].push_back(h-2),G[to].push_back(h-1);
}
bool bfs(){
	memset(vis,0,sizeof(vis));
	queue<int>q;
	vis[s]=1,d[s]=0,q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<(int)G[u].size();i++){
			Edge e=edges[G[u][i]];
			if(!vis[e.to]&&e.cap>e.flow)vis[e.to]=1,d[e.to]=d[u]+1,q.push(e.to);
		}
	}
	return vis[t];
}
int dfs(int x,int v){
	if(x==t||!v)return v;
	int f,flow=0;
	for(int&i=cur[x];i<(int)G[x].size();i++){
		Edge&e=edges[G[x][i]];
		if(d[e.to]==d[x]+1&&(f=dfs(e.to,min(v,e.cap-e.flow)))){
			flow+=f,e.flow+=f,v-=f;
			edges[G[x][i]^1].flow-=f;
			if(!v)break;
		}
	}
	return flow;
}
int dinic(){
	int flow=0;
	while(bfs()){
		memset(cur,0,sizeof(cur));
		flow+=dfs(s,inf);
	}
	return flow;
}
int main(){
	freopen("destroyingthegraph.in","r",stdin);
	freopen("destroyingthegraph.out","w",stdout);
	scanf("%d%d",&n,&m);
	int u,v;s=0,t=n*2+1;
	for(int i=1;i<=n;i++)scanf("%d",&u),addedge(i+n,t,u);
	for(int i=1;i<=n;i++)scanf("%d",&u),addedge(s,i,u);
	for(int i=1;i<=m;i++)scanf("%d%d",&u,&v),addedge(u,v+n,inf);
	int ans=dinic();
	printf("%d\n",ans);
	return 0;
}