基础题。
最小割后，与汇点相连的点都不要，然后从源点出发dfs一遍有多少相连的点即可。
#include<stdio.h> #include<string.h> #include<queue> #define INF 99999999 #define ll __int64 using namespace std; const int maxn = 5100; struct node { int to; ll v; int flag; int next; }edge[(60000+maxn)*2]; int index,pre[maxn],vis[maxn],S,T,cnt; void add(int x,int y,int z) { edge[index].to=y; edge[index].v=z; edge[index].flag=index+1; edge[index].next=pre[x]; pre[x]=index++; edge[index].to=x; edge[index].v=0; edge[index].flag=index-1; edge[index].next=pre[y]; pre[y]=index++; } ll dfs(int u,ll low) { int i; ll used=0; if(u==T) return low; for(i=pre[u];i!=-1&&used<low;i=edge[i].next) { if(edge[i].v&&vis[edge[i].to]==vis[u]+1) { ll a=dfs(edge[i].to,min(edge[i].v,low-used)); edge[i].v-=a; edge[edge[i].flag].v+=a; used+=a; } } if(!used) vis[u]=-1; return used; } int BFS() { int i; memset(vis,-1,sizeof(vis)); queue<int>q; vis[0]=1; q.push(0); while(!q.empty()) { int t=q.front(); q.pop(); for(i=pre[t];i!=-1;i=edge[i].next) { if(edge[i].v&&vis[edge[i].to]<0) { vis[edge[i].to]=vis[t]+1; q.push(edge[i].to); } } } if(vis[T]>0) return 1; return 0; } void cnt_dfs(int u) { cnt++; vis[u]=1; for(int i=pre[u];i!=-1;i=edge[i].next) { if(!vis[edge[i].to]&&edge[i].v) { cnt_dfs(edge[i].to); } } } int main() { int n,m,i; while(~scanf("%d%d",&n,&m)) { cnt=0; ll sum=0; index=1; memset(pre,-1,sizeof(pre)); for(i=1;i<=n;i++) { ll x; scanf("%I64d",&x); if(x>0) { sum+=x; add(0,i,x); } else add(i,n+1,-x); } for(i=0;i<m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y,INF); } ll ans=0; S=0,T=n+1; while(BFS()) {
while(1){ ll a=dfs(0,INF); if(!a)break; ans+=a;
} } memset(vis,0,sizeof(vis)); cnt_dfs(0); printf("%d %I64d ",cnt-1,sum-ans); } }