Firing

题目：

要解雇一些人，而解雇的这些人假设人跟他有上下级的关系，则跟他有关系的人也要一起解雇。每一个人都会创造一定的价值，要求你求出在最大的获利下。解雇的人最小。

算法分析：

在这之前要知道一个定理：

最小割 = 最大流

一道最大权闭合图的裸题，而这又能够转换成最小割来求解。证明能够看2007年胡伯涛的论文则能够直接套出模板。没看过的最好去看一下。那里解释的清楚。

这里我给出他的原文的一些构造方法。

添加源s汇t

源s连接原图的正权点，容量为对应点权

原图的负权点连接汇t。容量为对应点权的相反数

原图边的容量为正无限.

而这里事实上最难的是第一问。而因为本人的实力有限。所以，难以解释清楚。

可是网上流传的该题解题报告的人非常少有解释清的，都是一笔带过。找了好久才找到了一篇正确的解释。以下给出解释。

////////////////////////////////////////////////////////////////

标准的最大权闭合图，构图：从源点s向每一个正收益点连边，容量为收益；从每一个负收益点向汇点t连边，容量为收益的相反数；对于i是j的上司，连边i->j，容量为inf。最大收益 = 正收益点权和 - 最小割 = 正收益点权和 - 最大流（胡波涛论文上有证明）。这题的关键是怎样在最小割的前提下求出最少的割边数目，能够从源点对残量网络进行一次DFS，每一个割都会将源汇隔开，所以从源点DFS下去一定会由于碰到某个割而无法前进，用反证法易知这时遍历过的点数就是S集的最少点数。

/////////////////////////////////////////////////////////////////

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 5000 + 10;

const LL INF = (1LL) << 60;       //必须(1LL)!!!!!!!!!!!!!!!!!!!!  T_T......

struct Edge{

   int from,to;

   LL cap,flow;

   Edge(){};

   Edge(int _f,int _t,LL _c,LL _fw)

        :from(_f),to(_t),cap(_c),flow(_fw){};

};

vector<Edge> edges;

vector<int> G[MAXN];

bool vst[MAXN];

int d[MAXN],cur[MAXN];

int V,E,S,T;

int cnt;         //最少割边数

LL ans,sum;

void clr(){

    ans = sum = 0;

    S = 0; T = V + 1;

    for(int i = 0;i <= V;++i)

        G[i].clear();

    edges.clear();

}

void addEdge(int f,int t,LL cap){

    edges.push_back(Edge(f,t,cap,0));

    edges.push_back(Edge(t,f,0,0));

    int sz = edges.size();

    G[f].push_back(sz - 2);

    G[t].push_back(sz - 1);

}

void init(){

    LL x;

    for(int i = 1;i <= V;++i){

        scanf("%I64d",&x);

        if(x > 0){

            addEdge(S,i,x);

            sum += x;

        } else {

           addEdge(i,T,-x);

        }

    }

    int a,b;

    for(int i = 0;i < E;++i){

        scanf("%d%d",&a,&b);

        addEdge(a,b,INF);

    }

}

bool BFS(){

   memset(vst,0,sizeof(vst));

   queue<int> Q;

   Q.push(S);

   d[S] = 0;

   vst[S] = 1;

   while(!Q.empty()){

      int x = Q.front();  Q.pop();

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

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

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

              vst[e.to] = 1;

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

              Q.push(e.to);

          }

      }

   }

   return vst[T];

}

LL DFS(int x,LL a){

   if(x == T||a == 0)

      return a;

   LL flow = 0,f;

   for(int& i = cur[x];i < (int)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))) > 0){

           e.flow += f;

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

           flow += f;

           a -= f;

           if(a == 0) break;

       }

   }

   return flow;

}

LL Maxflow(){

   LL flow = 0;

   while(BFS()){

       memset(cur,0,sizeof(cur));

       flow += DFS(S,INF);

   }

   return flow;

}

//求解在最小割的前提下，得最好割边

void dfs(int u){

   vst[u] = 1;

   for(int i = 0;i < (int)G[u].size();++i){

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

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

         cnt++;

         dfs(e.to);

      }

   }

}

void solve(){

    LL ans = sum - Maxflow();

    cnt = 0;

    memset(vst,0,sizeof(vst));

    dfs(S);

    printf("%d %I64d\n",cnt,ans);

}

int main()

{

   // freopen("Input.txt","r",stdin);

    while(~scanf("%d%d",&V,&E)){

        clr();

        init();

        solve();

    }

    return 0;

}