Firing

Description

You’ve finally got mad at “the world’s most stupid” employees of yours and decided to do some firings. You’re now simply too mad to give response to questions like “Don’t you think it is an even more stupid decision to have signed them?”, yet calm enough to consider the potential profit and loss from firing a good portion of them. While getting rid of an employee will save your wage and bonus expenditure on him, termination of a contract before expiration costs you funds for compensation. If you fire an employee, you also fire all his underlings and the underlings of his underlings and those underlings’ underlings’ underlings… An employee may serve in several departments and his (direct or indirect) underlings in one department may be his boss in another department. Is your firing plan ready now?

Input

The input starts with two integers n (0 < n ≤ 5000) and m (0 ≤ m ≤ 60000) on the same line. Next follows n + m lines. The first n lines of these give the net profit/loss from firing the i-th employee individually bi (|bi| ≤ 107, 1 ≤ i ≤ n). The remaining m lines each contain two integers i and j (1 ≤ i, j ≤ n) meaning the i-th employee has the j-th employee as his direct underling.

Output

Output two integers separated by a single space: the minimum number of employees to fire to achieve the maximum profit, and the maximum profit.

Sample Input

5 5
8
-9
-20
12
-10
1 2
2 5
1 4
3 4
4 5

Sample Output

2 2

Hint

As of the situation described by the sample input, firing employees 4 and 5 will produce a net profit of 2, which is maximum.
題意：
公司要裁員，裁掉一個員工，他的下屬也得裁掉。裁掉一個員工可以少發一定的工資，但他已經他的下屬全被裁掉，所以這個partment會減少一定的生產利潤。顯然，裁掉一個人就可能得到收益（正的或者負的）；
給出裁掉一個員工能獲得的收益（正或負）。
給出公司里員工的依賴關系。表示A有下屬B
問得到的最大利益以及裁掉的最少人數。
分析：在這些人中選若干人，使得收益最大。如果A有下屬B，那我裁掉A就得裁掉B。所以裁掉B成了裁掉A的必要條件，即A依賴于B。所以讓A連向B，A->B容量為正無窮。
那么選若干人事效益最大就是求這個權閉合圖的最大值。
之后對于收益是正的人，s->x容量為收益值，對于收益是負的人x->t，容量為收益值得絕對值。
結果就是正權值和-最小割值（最大流：圖中切割最小的值）=最大權閉合圖的值。
這個圖從s出發的邊都是收益，從x->t的邊都是消耗。那求最小割就是對于給出的這么多的收益，通過多少消耗能讓取得的收益最大。
那最后的利潤就是：總利潤和-取得利潤最大所需的消耗。
#include <iostream>
#include <stdlib.h>
using namespace std;
const int maxn= 20010;
const __int64 inf=0x7fffffff;
struct node
{
    __int64 v,next;
    __int64 w;
}fn[500010];
__int64 level[maxn],g[maxn],que[maxn],out[maxn],th, tip, visit[maxn];
inline void add(__int64 u,__int64 v,__int64 w)
{
    fn[th].v = v, fn[th].w = w, fn[th].next = g[u], g[u] = th++;    
    fn[th].v = u, fn[th].w = 0, fn[th].next = g[v], g[v] = th++;
}
void build_level(__int64  n,__int64 s,__int64  e)
{
    __int64 h=0,r=0,i,u;    
    for (i = 0; i <= n; i++) level[i]=0;
    level[s] = 1;
    que[0] = s;
    while(h <= r)
    {
        u = que[h++];
        for (i = g[u]; i != -1; i = fn[i].next)
        {
            if (fn[i].w && level[fn[i].v] == 0)
            {
                que[++r] = fn[i].v;
                level[fn[i].v] = level[u] + 1;
             }
        }
    }
 }
__int64 dinic(__int64 n,__int64 s,__int64 e)
{
    __int64 ret=0,i;
    while(1)
    {
        build_level(n,s,e);
        if (level[e] == 0) break;
        for (i = 0; i < n; ++i) out[i] = g[i];
        __int64 q = -1;
        while(1)
        {
            if (q < 0)
            {
                for (i = out[s]; i != -1; i = fn[i].next)
                {
                    if (fn[i].w && out[fn[i].v] != -1 && level[fn[i].v] == 2)
                    {
                        que[++q] = i;
                        out[s] = fn[i].next;
                        break;
                    }
                }
                if (i == -1)
                {
                    break;
                }
            }
            __int64 u = fn[que[q]].v;
            if(u == e)
            {
                __int64 tmp=inf;
                for(i = 0;i <= q; i++)
                    if(tmp > fn[que[i]].w)tmp = fn[que[i]].w;
                ret += tmp;
                for(i=0;i<=q;i++)
                {
                    fn[que[i]].w -= tmp;
                    fn[que[i]^1].w += tmp;   
                }
                for (i = 0; i <= q; i++)
                {
                    if(fn[que[i]].w == 0)
                    {
                        q = i-1;
                        break;
                    }
                }
            }
            else
            {
                for (i = out[u]; i != -1; i = fn[i].next)
                {
                    if (fn[i].w && out[fn[i].v] !=-1 && level[u] + 1 == level[fn[i].v]) 
                    {
                        que[++q] = i, out[u] = fn[i].next;
                        break;
                    }
                }
                if(i==-1)
                {
                    out[u] = -1, q--;
                 }
              
            }
        }
    }
    return ret;
}
void dfs(int s, int e)
{
    int i;
    if (s == e)
    {
        return;
    }
    for (i = g[s]; i != -1; i++)
    {
        if (!visit[fn[i].v] && fn[i].w)
        {
            dfs(fn[i].v, e);
        }
    }
}
int main()
{
    __int64 m, n, t, u, v, i, j, start, end, sum, num, w, ans;
    int k = 0;
    while (scanf("%I64d%I64d", &n, &m) - EOF)
    {
        k++;
        start = 0, end = n + 1, th = 0;
        for (i = 0; i <= end; i++)
        {
            g[i] = -1;
        }
        for (i = 1, sum = 0; i <= n; i++)
        {
            scanf("%I64d", &num);
            if (num >= 0)
            {
                add(start, i, num);
                sum += num;
            }
            else
            {
                add(i, end, -num);
            }
        }
        for (j = 1; j <= m; j++)
        {
            scanf("%I64d%I64d", &u, &v);
            add(u, v, inf);
        }
        sum -= dinic(end + 1, start, end);
        tip = 0;
        for (i = 0; i <= end + 1; i++)
        {
            visit[i] = 0;
        }
        dfs(0, end);
        for (i = 0, tip = 0; i <= end + 1; i++)
        {
            if (visit[i])
            {
                tip++;
            }
        }
        printf("%I64d %I64d\n", tip, ans);
    }
    //system("pause");
    return 0;
}