记录编号	94715	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2003][POJ2125]有向图破坏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2014-04-02 17:05:31	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=310,INF=0x7fffffff/2;
class EDGE{
public:
	int from,to,cap,flow;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
bool visit[SIZEN]={0};//在需要找割集的时候就把这个放在外面
int S,T,N;//0~N
int depth[SIZEN]={0};
int cur[SIZEN]={0};
void addedge(int from,int to,int cap){
	EDGE temp;
	temp.from=from,temp.to=to,temp.cap=cap,temp.flow=0;
	edges.push_back(temp);
	temp.from=to,temp.to=from,temp.cap=0,temp.flow=0;
	edges.push_back(temp);
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
bool BFS(void){
	memset(visit,0,sizeof(visit));
	queue<int> Q;
	Q.push(S);visit[S]=true;depth[S]=0;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			EDGE &now=edges[c[x][i]];
			if(!visit[now.to]&&now.cap>now.flow){
				visit[now.to]=true;
				depth[now.to]=depth[x]+1;
				Q.push(now.to);
			}
		}
	}
	return visit[T];
}
int DFS(int x,int a){
	if(x==T||!a) return a;
	int flow=0,cf=0;
	for(int i=cur[x];i<c[x].size();i++){
		cur[x]=i;
		EDGE &now=edges[c[x][i]];
		if(depth[x]+1==depth[now.to]){
			cf=DFS(now.to,min(a,now.cap-now.flow));
			if(cf){
				flow+=cf;
				a-=cf;
				now.flow+=cf,edges[c[x][i]^1].flow-=cf;
			}
			if(!a) break;
		}
	}
	if(!flow) depth[x]=-1;
	return flow;
}
int Dinic(void){
	int flow=0;
	while(BFS()){
		memset(cur,0,sizeof(cur));
		flow+=DFS(S,INF);
	}
	return flow;
}
int n,m;
void work(void){
	int anscost,numopt=0;
	anscost=Dinic();
	printf("%d\n",anscost);
	return;
	//下面是输出方案的内容
	BFS();
	for(int i=1;i<=n;i++) if(!visit[i]) numopt++;//T~这条边
	for(int i=n+1;i<=2*n;i++) if(visit[i]) numopt++;//这条边~T
	printf("%d\n%d\n",anscost,numopt);
	for(int i=1;i<=n;i++){
		if(!visit[i]) printf("%d -\n",i);
		if(visit[i+n]) printf("%d +\n",i);
	}
}
void init(void){
	scanf("%d%d",&n,&m);
	S=0,T=N=2*n+1;
	int a,b,w;
	for(int i=1;i<=n;i++){
		scanf("%d",&w);//删除所有入边
		addedge(i+n,T,w);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&w);//删除所有出边
		addedge(S,i,w);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b+n,INF);//确保这条边不会被割掉
	}
}
int main(){
	freopen("destroyingthegraph.in","r",stdin);
	freopen("destroyingthegraph.out","w",stdout);
	init();
	work();
	return 0;
}