解题思路

1. 问题建模：

   • 将员工及其上下级关系建模为一个有向图，其中节点代表员工，边代表上下级关系（$i \rightarrow j$ 表示 $i$ 是 $j$ 的上级）。
   • 解雇一个员工会连带解雇其所有下属（直接或间接），因此需要选择一个闭合子图（closed subset），即选中某些节点后，其所有后继节点也必须被选中。

2. 关键观察：

   • 目标是选择一个闭合子图，使得子图中所有节点的 $b_i$ 之和最大。
   • 这是一个典型的最大权闭合子图问题，可以通过网络流中的最小割模型解决。

3. 网络流模型：

   • 源点 $s$：连接所有 $b_i > 0$ 的节点，容量为 $b_i$。
   • 汇点 $t$：所有 $b_i < 0$ 的节点连接到 $t$，容量为 $-b_i$。
   • 依赖关系：如果 $i$ 是 $j$ 的上级，则添加一条 $i \rightarrow j$ 的边，容量为无穷大（表示必须同时选中）。
   • 最大利润为所有正权值之和减去最小割的容量。

4. 求解步骤：

   • 构造网络流图。
   • 使用 Dinic 算法计算从 $s$ 到 $t$ 的最大流（即最小割）。
   • 最终利润为 $\sum_{b_i > 0} b_i - \text{min\_cut}$。
   • 通过残量网络 BFS 标记可达节点，统计最小解雇人数。

解题方法

1. 输入处理：

   • 读取 $n$ 和 $m$，以及每个员工的 $b_i$。
   • 读取 $m$ 条上下级关系，构建邻接表。

2. 网络流建图：

   • 源点 $s = 0$，汇点 $t = n + 1$。
   • 对于 $b_i > 0$ 的员工，添加边 $s \rightarrow i$，容量为 $b_i$。
   • 对于 $b_i < 0$ 的员工，添加边 $i \rightarrow t$，容量为 $-b_i$。
   • 对于每条上下级关系 $i \rightarrow j$，添加边 $i \rightarrow j$，容量为 $\infty$（代码中用 INF 表示）。

3. 计算最大流：

   • 使用 Dinic 算法计算从 $s$ 到 $t$ 的最大流（即最小割）。
   • 最大利润为 $\sum_{b_i > 0} b_i - \text{max\_flow}$。

4. 统计最少解雇人数：

   • 在残量网络上从 $s$ 开始 BFS，标记所有可达节点。
   • 被标记的节点（除 $s$ 外）即为需要解雇的员工，数量为 num - 1。

代码实现要点

• Dinic 算法：
  • BFS 分层：计算从源点的最短距离。
  • DFS 多路增广：在分层图上寻找增广路。
• 残量网络分析：
  • 通过 cal(u) 函数（基于 BFS）统计可达节点。
• 复杂度：
  • Dinic 算法的时间复杂度为 $O(n^2 m)$，但在实际稀疏图上表现良好。

##C++代码实现：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs id*2+1
#define Mod(a,b) a<b?a:a%b+b 
using namespace std;
 
const ll M = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5010;
const double e = 10e-6;
 
struct edge 
{ 
	int to;
	ll cap;
	int rev;
};
vector<edge>G[N];
int level[N], iter[N];
 
void addEdge(int from, int to, ll cap)
{
	G[from].push_back(edge{ to,cap,(int)G[to].size() });
	G[to].push_back(edge{ from,0,(int)G[from].size() - 1 });
}
 
void bfs(int s)
{
	memset(level, -1, sizeof(level));
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while (!que.empty()) {
		int v = que.front(); que.pop();
		int len = G[v].size();
		for (int i = 0; i < len; i++) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}
 
ll dfs(int v, int t, ll f)
{
	if (v == t)
		return f;
	int len = G[v].size();
	for (int &i = iter[v]; i < len; i++) {
		edge &e = G[v][i];
		if (e.cap > 0 && level[v] < level[e.to]) {
			ll d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	} 
	return 0;
}
 
ll maxFlow(int s, int t)
{
	ll flow = 0;
	while (1) {
		bfs(s);
		if (level[t] < 0)
			return flow;
		memset(iter, 0, sizeof(iter));
		ll f;
		while ((f = dfs(s, t, INF)) > 0)
			flow += f;
	}
}
 
int n, m, num;
bool vis[N];
 
void cal(int u)
{
	vis[u] = true;
	num++;
 
	int len = G[u].size();
	for (int i = 0; i < len; i++) {
		edge e = G[u][i];
		if (e.cap > 0 && !vis[e.to])
			cal(e.to);
	}
}
 
int main() {
	while (~scanf("%d%d", &n, &m)) {
		for (int i = 0; i <= n + 1; i++)
			G[i].clear();
		
		ll xx, ans = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%lld", &xx);
			if (xx > 0) {
				addEdge(0, i, xx);
				ans += xx;
			}
			else if (xx < 0)
				addEdge(i, n + 1, -xx);
		}
 
		int x, y;
		for (int i = 1; i <= m; i++) {
			scanf("%d%d", &x, &y);
			addEdge(x, y, INF);
		}
		
		ans -= maxFlow(0, n + 1);
 
		memset(vis, false, sizeof(vis));
		num = 0;
		cal(0);
 
		printf("%d %lld\n", num - 1, ans);
	}
 
	return 0;
}