【题意】:公司要炒一些员工的鱿鱼, 若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, -1sizeof(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, 00);
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, 0sizeof(cnt));
35     memset(low, 0sizeof(low));
36     memset(dist, 0sizeof(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] + 1break;
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]] == 0break;
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, falsesizeof(visit));
95     dfs(s);
96     printf("%d %lld\n", num, ans);
97 }