【题意】：公司要炒一些员工的鱿鱼, 若A被炒了, 那A的所有下属也会跟着被炒, 下属关系具有传递性, 且可能构成环, 即A是B的下属, B又间接是A的下属, 炒掉每个人公司会得到一笔收益, 收益可能为负, 问在收益最大的前提下, 最少要炒掉哪些人, 以及最大收益是多少.
【题解】：标准的最大权闭合图，构图：从源点s向每个正收益点连边，容量为收益；从每个负收益点向汇点t连边，容量为收益的相反数；对于i是j的上司，连边i->j，容量为inf。最大收益 = 正收益点权和 - 最小割 = 正收益点权和 - 最大流（胡波涛论文上有证明）。这题的关键是如何在最小割的前提下求出最少的割边数目，可以从源点对残量网络进行一次DFS，每个割都会将源汇隔开，所以从源点DFS下去一定会因为碰到某个割而无法前进，用反证法易知这时遍历过的点数就是S集的最少点数。
【代码】：
1 #include "iostream"
2 #include "cstring"
3 #include "cstdio"
4 using namespace std;
5 #define maxn 5005
6 #define maxm 100005
7 const int inf = 1 << 30;
8 int n, m, s, t;
9 int eh[maxn], dist[maxn], cur[maxn], pre[maxn], low[maxn], tot, cnt[maxn];
10 int w[maxn], num;
11 bool visit[maxn];
12
13 struct Edge {
14 int u, v, cap ,flow, next;
15 }et[maxm];
16
17 void init() {
18 tot = 0;
19 memset(eh, -1, sizeof(eh));
20 }
21
22 void add(int u, int v, int cap, int flow) {
23 Edge e = {u, v, cap, flow, eh[u]};
24 et[tot] = e, eh[u] = tot++;
25 }
26
27 void addedge(int u, int v, int cap) {
28 add(u , v, cap, 0), add(v, u, 0, 0);
29 }
30
31 long long isap(int s, int t, int n) {
32 int u, v, now;
33 long long flow = 0;
34 memset(cnt, 0, sizeof(cnt));
35 memset(low, 0, sizeof(low));
36 memset(dist, 0, sizeof(dist));
37 for(u = 0; u <= n; u++) cur[u] = eh[u];
38 low[s] = inf, cnt[0] = n;
39 u = s;
40 while(dist[s] < n) {
41 for(now = cur[u]; now != -1; now = et[now].next)
42 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
43 if(now != -1) {
44 cur[u] = pre[v] = now;
45 low[v] = min(low[u], et[now].cap - et[now].flow);
46 u = v;
47 if(u == t) {
48 for(; u != s; u = et[pre[u]].u) {
49 et[pre[u]].flow += low[t];
50 et[pre[u]^1].flow -= low[t];
51 }
52 flow += low[t], low[s] = inf;
53 }
54 } else {
55 if(--cnt[dist[u]] == 0) break;
56 dist[u] = n;
57 cur[u] = eh[u];
58 for(now = eh[u]; now != -1; now = et[now].next)
59 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
60 dist[u] = dist[et[now].v] + 1;
61 cnt[dist[u]]++;
62 if(u != s) u = et[pre[u]].u;
63 }
64 }
65 return flow;
66 }
67
68 void dfs(int u) {
69 visit[u] = true;
70 for(int i = eh[u]; i != -1; i = et[i].next)
71 if(et[i].cap - et[i].flow && !visit[et[i].v]) {
72 num++;
73 dfs(et[i].v);
74 }
75 }
76
77 int main() {
78 int u, v;
79 init();
80 scanf("%d%d", &n, &m);
81 s = 0, t = n + 1;
82 num = 0;
83 long long ans = 0;
84 for(int i = 1; i <= n; i++) {
85 scanf("%d", &w[i]);
86 if(w[i] > 0) addedge(s, i, w[i]), ans += w[i];
87 else if(w[i] < 0) addedge(i, t, -w[i]);
88 }
89 for(int i = 0; i < m; i++) {
90 scanf("%d%d", &u, &v);
91 addedge(u, v, inf);
92 }
93 ans -= isap(s, t, t - s + 1);
94 memset(visit, false, sizeof(visit));
95 dfs(s);
96 printf("%d %lld\n", num, ans);
97 }