POJ2987 Firing 最大权闭合图

详情请参考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 = ;

const int INF = 0x3f3f3f3f;

const LL mod = 1e9+;

const int maxn=5e3+;

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=;i<maxn;++i)G[i].clear();

      edges.clear();

    }

    bool bfs()

    {

        memset(vis,,sizeof(vis));

        queue<int>q;

        q.push(s);

        d[s]=;

        vis[s]=;

        while(!q.empty())

        {

            int x=q.front();

            q.pop();

            for(int i=; i<G[x].size(); i++)

            {

                Edge &e= edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.flow)

                {

                    vis[e.to]=;

                    d[e.to]=d[x]+;

                    q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    int dfs(int x,int a)

    {

        if(x==t||a==)return a;

        int flow=,f;

        for(int &i=cur[x]; i<G[x].size(); i++)

        {

            Edge &e=edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow))))

            {

                e.flow+=f;

                edges[G[x][i]^].flow-=f;

                flow+=f;

                a-=f;

                if(a==)break;

            }

        }

        return flow;

    }

    LL maxflow(int s,int t)

    {

        this->s=s;

        this->t=t;

        LL flow=;

        while(bfs())

        {

            memset(cur,,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,),y(v,u,,);

        edges.push_back(x);

        edges.push_back(y);

        int l=edges.size();

        G[u].push_back(l-);

        G[v].push_back(l-);

    }

    int search(int u){

       int ret=;vis[u]=true;

       for(int i=;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=;

     for(int i=;i<=n;++i){

       int w;scanf("%d",&w);

       if(w>)sum+=w,solve.addedge(,i,w);

       else if(w<)solve.addedge(i,n+,-w);

     }

     for(int i=;i<m;++i){

      int u,v;scanf("%d%d",&u,&v);

      solve.addedge(u,v,INF);

     }

     LL mxf=solve.maxflow(,n+);

     printf("%d %I64d\n",solve.search()-,sum-mxf);

  }

  return ;

}