最大闭合子图

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
typedef long long LL;
const int N=100005;
const int INF=0x3f3f3f3f;
int n,m,tot,vt,vs;
int d[N],head[N];
struct lp{
	int to,w,nex;
	lp(){}
	lp(int a,int b,int c){
		to=a;w=b;nex=c;
	}
}cw[N<<2];
int pigNum[N],pigTo[N];
inline void add(int a,int b,int c){
	cw[++tot]=lp(b,c,head[a]);
	head[a]=tot;
	cw[++tot]=lp(a,0,head[b]);
    head[b]=tot;
}
bool bfs(){
   memset(d,-1,sizeof(d)); 
    queue<int>Q;
    Q.push(vt);d[vt]=0;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
		for (int i=head[u];i!=-1;i=cw[i].nex){
			int v=cw[i].to;
			if (cw[i^1].w&&d[v]==-1){
				d[v]=d[u]+1;
				Q.push(v);
			}
		}
	}
    return d[vs]!=-1;
}
int dfs(int x,int f){
	if (x==vt||f==0) return f;
	int use=0,w;
	for (int i=head[x];i!=-1;i=cw[i].nex){
		int to=cw[i].to;
		if (d[to]==d[x]-1&&cw[i].w){
			w=dfs(to,min(cw[i].w,f-use));
			cw[i].w-=w,cw[i^1].w+=w;
			use+=w;
			if (use==f) return f; 
		}
	}
  return use;
}
inline void init(){
   tot=-1;
   memset(head,-1,sizeof(head));
   memset(pigTo,0,sizeof(pigTo)); 
   vs=0,vt=n+1;
}
int main(){
	int x,y;
	scanf("%d",&n);
	init();
	int sum=0;
	for (int i=1;i<=n;i++)
	{
	   scanf("%d%d",&x,&y);
	   if (x-y>0){
	   	  sum+=x-y;
	   	  add(vs,i,x-y);
	   }else{
	   	  add(i,vt,y-x);
	   }
	}
	while (~scanf("%d%d",&x,&y)){
		add(y,x,INF);
	}
	int ans=0;
	while(bfs()) ans+=dfs(vs,INF);
	printf("%d\n",sum-ans);
	return 0;
}