C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 944K, 提交时间: 2020-07-22 13:27:52

#include<bits/stdc++.h>
#define min(a,b) a<b?a:b
#define nx 100005
using namespace std;
int h[505],to[nx],c[nx],nxt[nx],cnt=1;
int cur[505],dis[505],val[505],n,m,s,t;
inline void add(int u,int v,int l){
	to[++cnt]=v,c[cnt]=l,nxt[cnt]=h[u],h[u]=cnt;
}
inline bool bfs(){
	memcpy(cur,h,sizeof h),memset(dis,0,sizeof dis);
	int q[505],f=1,r=0,now,v;
	q[++r]=s,dis[s]=1;
	while(f<=r){
		now=q[f++];
		for(int i=h[now];i;i=nxt[i])
			if(c[i]&&!dis[v=to[i]]){
				dis[v]=dis[now]+1,q[++r]=v;
				if(v==t)return 1;
			}
	}return 0;
}
inline int dfs(int x,int now){
	if(x==t||!now)return now;
	int re=0,f,v;
	for(int i=cur[x];i;i=nxt[i]){
		cur[x]=i;
		if(c[i]&&dis[v=to[i]]==dis[x]+1){
			f=dfs(v,min(now-re,c[i]));
			c[i]-=f,c[i^1]+=f,re+=f;
			if(now-re==0)break;
		}
	}return re;
}
int main(){
	scanf("%d",&n),s=n+1,t=n+2;
	int u,v;
	for(int i=1;i<=n;++i)
		scanf("%d%d",&u,&v),val[i]=u-v;
	while(~scanf("%d%d",&u,&v))
		add(v,u,505),add(u,v,0);
	int ans=0;
	for(int i=1;i<=n;++i){
		if(val[i]>0)ans+=val[i],add(s,i,val[i]),add(i,s,0);
		if(val[i]<0)add(i,t,-val[i]),add(t,i,0);
	}
	while(bfs())ans-=dfs(s,0x3f3f3f3f);
	printf("%d",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 273ms, 内存消耗: 2012K, 提交时间: 2018-05-04 16:09:13

#include <bits/stdc++.h>
using namespace std;
#define maxn 505
int n,u,v,f[maxn],in[maxn],ans;
bool line[maxn][maxn];
vector<int>Q[maxn];
set<vector<bool> >W;
vector<bool>path;
void DFS(int num)
{
    if(W.count(path)) return ;
    ans=max(ans,num);
    W.insert(path);
    for(int i=1;i<=n;i++)
    {
        if(path[i]){
            for(int j=0;j<Q[i].size();j++){
                if(-- in[Q[i][j]] == 0) path[Q[i][j]]=1;
            } path[i]=0;
            DFS(num+f[i]);
            for(int j=0;j<Q[i].size();j++){
                if(!in[Q[i][j]]) path[Q[i][j]]=0;
                in[Q[i][j]]++;
            } path[i]=1;
        }
    }
}
int main()
{
    cin>>n;ans=0;
    for(int i=1;i<=n;i++) {cin>>u>>v;f[i]=u-v;}
    while(cin>>u>>v){
        in[v]++;
        Q[u].push_back(v);
    }
    path = vector<bool>(n+1,0);
    for(int i=1;i<=n;i++) if(!in[i]) path[i]=1;
    DFS(0); cout<<ans<<endl;
    return 0;
}