题意不难。
思路很容易想到用网络流的模型。把那些关联关系用单向边来连接，但是没想好是怎么处理出最优解。
都说用最大权闭合图。查了一下相关内容。
我的理解是：其实也是流网络的应用。特殊的地方在于每个点的权值的转化：
权值为正的接连源点S，权值为负的连接汇点T。中间的党羽单向边权值都为inf。
原理即是把所有正权值看成整体，负权值看成整体。
从源点尽情地充入流（正权值而连成的边），然后经过汇点的消耗（负权值），这样我们要的最大权值则是
正权值和-负权值和。
最大流最小割，即最大流的值刚好是最小割，此时的最小割正好是负权值和的最小值，刚好使上式值最大。
故得到最大权值。
接下来就是算最小割时候的最少点，即第一问。
从源点dfs去搜索残留网络，因为和源点连接的点都是权值为正的，是我们要解雇的人的集合，如果残留网络的边还为正，则这时候则表示fire这个点可以有收益。
然后dfs他的党羽。
这样将所有可以收益和他的党羽求和。
则是我们要的结果。
不懂的可以具体画几个例子就容易明白了。
最后祝国庆快乐。
#include<iostream>
#define llong long long
using namespace std;
const int N=5005;
const int M=60005;
const llong inf=(1ll)<<60;
int n,m;
struct Edge
{
int v;
llong w;
int next,re;
}edge[2*M];
int edgehead[N];
int k=1;
int level[N];
int que[N];
int visit[N];
int count;
void addedge(int u,int v,llong w)
{
edge[k].w=w;
edge[k].v=v;
edge[k].next=edgehead[u];
edge[k].re=k+1;
edgehead[u]=k++;
edge[k].w=0;
edge[k].v=u;
edge[k].next=edgehead[v];
edge[k].re=k-1;
edgehead[v]=k++;
}
bool bfs()
{
memset(visit,0,sizeof(visit));
memset(level,0,sizeof(level));
int head=1,tail=1;
int now=0;
que[tail++]=0;
visit[0]=true;
level[0]=0;
while(head<tail)
{
now=que[head++];
if(now==n+1)
return true;
for(int i=edgehead[now];i;i=edge[i].next)
{
int v=edge[i].v;
if(!visit[v]&&edge[i].w)
{
visit[v]=true;
level[v]=level[now]+1;
que[tail++]=v;
}
}
}
return false;
}
llong dinic(int now,llong sum)
{
if(now==n+1)
return sum;
llong os=sum;
for(int i=edgehead[now];i&&sum>0;i=edge[i].next)
{
int v=edge[i].v;
if(level[now]+1==level[v]&&edge[i].w>0)
{
llong tmp=dinic(v,(edge[i].w<sum?edge[i].w:sum));
edge[i].w-=tmp;
edge[edge[i].re].w+=tmp;
sum-=tmp;
}
}
return os-sum;
}
llong solve(llong sum)
{
llong ans=0;
while(bfs())
{
ans+=dinic(0,inf);
}
// printf("%lld\n",sum-ans);
return sum-ans;
}
void dfs(int now)
{
visit[now]=true;
count++;
for(int i=edgehead[now];i;i=edge[i].next)
{
int v=edge[i].v;
if(edge[i].w&&!visit[v])//非残留网络的边
{
dfs(v);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
llong w;
llong sum=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&w);
if(w>=0)
{
addedge(0,i,w);
sum+=w;
}
else
{
addedge(i,n+1,-w);
}
}
int from,to;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&from,&to);
addedge(from,to,inf);
}
llong ans=solve(sum);
memset(visit,0,sizeof(visit));
dfs(0);
printf("%d %lld\n",count-1,ans);
return 0;
}