Submission #37361205

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005,M=3005;
int tot=1,linkk[N],en,dep[N];
struct Edge{int y,z,nex;}e[M];
bool bfs(){
	memset(dep,-1,sizeof(dep));queue<int> q;
	dep[0]=0;q.push(0);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=linkk[x];i;i=e[i].nex){
			if(dep[e[i].y]>=0||!e[i].z)continue;
			dep[e[i].y]=dep[x]+1,q.push(e[i].y);
		}
	}
	return dep[en]>=0;
}
int dfs(int x,int in){
	if(x==en)return in;
	int ans=0;
	for(int i=linkk[x];i&&in;i=e[i].nex){
		int y=e[i].y,z=e[i].z;
		if(dep[y]!=dep[x]+1||!z)continue;
		int t=dfs(y,min(z,in));
		in-=t,ans+=t,e[i].z-=t,e[i^1].z+=t;
	}
	if(!ans)dep[x]=-1;
	return ans;
}
void ling(int x,int y,int z){e[++tot]=(Edge){y,z,linkk[x]};linkk[x]=tot;}
void add(int x,int y,int z){ling(x,y,z),ling(y,x,0);}
int ans,n,m,a[N],b[N];
signed main(){
	cin>>n>>m;en=2*n+1;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		cin>>b[i];ans+=abs(b[i]);
		add(i,i+n,a[i]+abs(b[i]));
		if(b[i]<0)add(i+n,en,-2*b[i]);
		else add(0,i,2*b[i]);
	}
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		add(x+n,y,1e9),add(y+n,x,1e9);
	}
	while(bfs())ans-=dfs(0,1e9);
	cout<<ans<<'\n';
}

Submission Info

Judge Result