题目链接：http://poj.org/problem?id=2987

题目大意：某公司想要裁员，裁员的标准是如果某人被裁，那么其下属也会被裁，依此类推，每一个人都有一个贡献度，如果为正，裁掉会增加公司的收益，如果为负，裁掉会减少公司的收益，问怎样裁员才能使得最后的贡献度最大并且裁掉人数最少？

思路：因为删掉一个上司，员工也会离开，所以最后求的删除的人会是一个闭合图，也就是求最大权闭合图。其中s集合所在的点就是最大权闭合图中的点。

1.先记录整个图中，所有正点权值的和；
2.建立对应流网络，求最大流，最大流在数值上等于最小割，故我们得到了流网络的s-t最小割；
3.“所有正点权值的和”减去“s-t最小割”，即得最大权闭合子图的权值和。
4.最小割图的点就是割去的点数

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxn=1e5+10;
const LL maxm=2e5+10;

struct E
{
    LL v;   //每一条边指向的点
    LL next;//指向对应点的前一条边
    LL w;   //每一条边的残量

}e[maxm];

LL s, t;//源点和汇点
LL cut;//边的数量，从0开始编号
LL head[maxm];//每一个点最后一条边的编号
LL d[maxn];//分层图中标记深度
LL inf=(1ll<<60);
LL cur[maxn];//cur就是记录当前点u循环到了哪一条边
LL n, m;

void init()
{
    cut=-1;
    memset(head, -1, sizeof(head));
}

void addEdge(LL u, LL v, LL w)
{
    cut++;
    e[cut].next=head[u];
    e[cut].v=v;
    e[cut].w=w;
    head[u]=cut;
}

void add(LL u, LL v, LL w)
{
    addEdge(u, v, w);
    addEdge(v, u, 0);
}

LL bfs()
{
    queue<LL> q;
    while(!q.empty())
    {
        q.pop();
    }
    memset(d, 0, sizeof(d));
    d[s]=1;//源点深度为1
    q.push(s);
    while(!q.empty())
    {
        LL u=q.front();
        q.pop();
        for(LL i=head[u];i!=-1;i=e[i].next)
        {
            LL v=e[i].v, w=e[i].w;
            if(w>0&&d[v]==0)//若该残量不为0，且V[i]还未分配深度，则给其分配深度并放入队列
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    if(d[t]==0)//当汇点的深度不存在时，说明不存在分层图，同时也说明不存在增广路
    {
        return 0;
    }

    return 1;
}

LL dfs(LL u, LL dis)//u是当前节点，dist是当前流量
{
    if(u==t)
    {
        return dis;//当已经到达汇点，直接返回
    }

    for(LL &i=cur[u];i!=-1;i=e[i].next)
    {
        LL v=e[i].v, w=e[i].w;
        if((d[v]==d[u]+1)&&w!=0)//注意这里要满足分层图和残量不为0两个条件
        {
            LL di=dfs(v, min(dis, w));//向下增广
            if(di>0)//若增广成功
            {
                e[i].w-=di;//正向边减
                e[i^1].w+=di;//反向边加
                return di;//向上传递
            }
        }
    }

    return 0;//否则说明没有增广路，返回0
}

LL Dinic()
{
    LL ans=0;//记录最大流量
    while (bfs())
    {
        /*******************************/
        for(LL i=s;i<=t;i++)//每一次建立完分层图后都要把cur置为每一个点的第一条边
        {
            cur[i]=head[i];
        }
        /********************************/
        while (LL d=dfs(s,inf))
        {
            ans+=d;
        }
    }
    return ans;
}

queue<int> q;
LL minzxg(){//不在最大权闭合子图的点数

    LL ans=0;
    memset(d, 0, sizeof(d));
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        LL u=q.front();
        q.pop();
        ans++;
        for(LL i=head[u];i!=-1;i=e[i].next){
            LL v=e[i].v, w=e[i].w;
            if(d[v]==0&&w>0){
                d[v]=1;
                q.push(v);
            }
        }
    }
    return ans-1;//-源点
}

int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        init();
        s=0, t=n+1;
        LL u, v, w, ans=0;
        for(int i=1; i<=n; i++){
            scanf("%lld", &w);
            if(w>=0){
                ans+=w;
                add(s, i, w);
            }
            else{
                add(i, t, -w);
            }
        }
        for(int i=0;i<m;i++)
        {
            LL u, v;
            scanf("%lld%lld",&u,&v);
            add(u, v, inf);
        }
        LL ds=Dinic();
        printf("%lld %lld\n",minzxg(), ans-ds);

    }
    return 0;
}