详情请参考http://www.cnblogs.com/kane0526/archive/2013/04/05/3001557.html
值得注意的地方，割边会把图分成两部分，一部分和起点相连，另一部分和汇点相连
我们只需要关注和起点相连的点的点就好，如何统计呢？
只需要从起点开始搜索，只要边不是满流，一直搜就好
然后，答案就是总权值-最小割
注：对于dinic网络流，我还是喜欢LRJ白书上的，用起来方便
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <map> #include <queue> #include <vector> using namespace std; typedef long long LL; const int N = 20; const int INF = 0x3f3f3f3f; const LL mod = 1e9+7; const int maxn=5e3+5; struct Edge { int from,to,cap,flow; Edge(int u,int v,int c,int d):from(u),to(v),cap(c),flow(d) {} }; struct dinic { int s,t; vector<Edge>edges; vector<int>G[maxn]; int d[maxn]; int cur[maxn]; bool vis[maxn]; void init(){ for(int i=0;i<maxn;++i)G[i].clear(); edges.clear(); } bool bfs() { memset(vis,0,sizeof(vis)); queue<int>q; q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0; i<G[x].size(); i++) { Edge &e= edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; q.push(e.to); } } } return vis[t]; } int dfs(int x,int a) { if(x==t||a==0)return a; int flow=0,f; for(int &i=cur[x]; i<G[x].size(); i++) { Edge &e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0)break; } } return flow; } LL maxflow(int s,int t) { this->s=s; this->t=t; LL flow=0; while(bfs()) { memset(cur,0,sizeof(cur)); flow+=dfs(s,INF); } memset(vis,false,sizeof(vis)); return flow; } void addedge(int u,int v,int c) { Edge x(u,v,c,0),y(v,u,0,0); edges.push_back(x); edges.push_back(y); int l=edges.size(); G[u].push_back(l-2); G[v].push_back(l-1); } int search(int u){ int ret=1;vis[u]=true; for(int i=0;i<G[u].size();++i){ Edge &e=edges[G[u][i]]; if(vis[e.to]||e.flow==e.cap)continue; ret+=search(e.to); } return ret; } }solve; int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ solve.init();LL sum=0; for(int i=1;i<=n;++i){ int w;scanf("%d",&w); if(w>0)sum+=w,solve.addedge(0,i,w); else if(w<0)solve.addedge(i,n+1,-w); } for(int i=0;i<m;++i){ int u,v;scanf("%d%d",&u,&v); solve.addedge(u,v,INF); } LL mxf=solve.maxflow(0,n+1); printf("%d %I64d ",solve.search(0)-1,sum-mxf); } return 0; }