这题可以应用经典的“最大权封闭子图”来解决，
方法是借用最大流——最小割定理，转化为：
如果一个数b[i]是正的，和源点连一个容量为A[i]的边，
如果一个数b[i]是负的，和源点连一个容量为-A[i]的边，
如果一个点x依赖于点y（也就是，要辞退x必须辞退y），那么就从x向y连一条
容量∞的边。
之后，跑一遍网络流，设答案为r，则b[i]中所有正数之和-r即为所求。

这题的特殊之处就是要输出最少辞退员工数。
怎么办呢？

利用一个经典的trick:多关键字
建图前，对所有b[i]，执行变换b[i]=b[i]*10000-1，然后，会惊异地发现，
此时最大流所对应的方案就是满足辞退最少人数的了。
为什么？显然，变换后的流量r2除以10000后再取整就等于原来的流量，但是
r2的后四位却蕴含了辞退人数的信息：每多辞退一个人，流量就会少1。

剩下的就是如何根据一个网络流输出方案。
我的做法：从源点开始沿着残余网络dfs（只走没有满载的边），
能dfs到的点对应的人就是需要辞退的。

网络流的算法我使用的是“有提交就会有奇迹”的dinic，实践证明，过了。
如果没有过，友情提示：动态开内存往往导致tle。

其实，写dinic是有技巧的，以下是我喜欢的19行版dinic
//这是数组以及结构定义，不计算行数
int level[NMax+2],queue[NMax+2];
long long Min(long long a,long long b){
	return a>b?b:a;
}
struct edge{
	long long e,f;
	edge *next,*opt;
}*E[NMax];

//正文
int mkLevel(){
	for (int i=0;i<N;i++)level[i]=-1;
	int bot,x;
	level[queue[0]=0]=0;bot=1;
	for (int top=0;top<bot;top++){x=queue[top];
		for (edge *p=E[x];p;p=p->next)if (p->f && level[p->e]==-1)
			level[queue[bot++]=p->e]=level[x]+1;
	}
	return level[N-1]!=-1;
}
long long extend(int x,long long alpha){
	if (x==N-1)return alpha;
	long long r,t;r=0;
	for (edge *p=E[x];p;p=p->next)if (p->f && level[p->e]==level[x]+1)
		t=extend(p->e,Min(p->f,alpha-r)),p->f-=t,p->opt->f+=t,r+=t;
	if (!r)level[x]=-1;
	return r;
}
void Dinic(){while (mkLevel())extend(0,(long long)1<<60);}

• 最大流求出来的最大权闭合子图已经可以保证最小点数了，没有必要变换边权 (1458) toomanynb 2009-12-13 19:33:50
• Re:雁过留声——最大权封闭子图 (12) glissng 2009-12-18 22:37:03
  • Re:为什么不放大边权，从源点dfs得到的集合就是最小点集？ (90) Headacher 2009-12-28 23:19:37
• 严重质疑LZ放大边权方式的正确性 (25) Snow_storm 2010-12-23 01:50:58
• 求完了可以不dfs吧 (94) bg95 2011-06-19 16:40:26