【題意】：公司要炒一些員工的魷魚, 若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 }