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;
}
