网络流-最大权闭合图（最小割求解）

http://poj.org/problem?id=2987

Description

Input

Output

Sample Input

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

Sample Output

2 2

Hint

题意：一个公司要开除一些员工，开除每个员工都会获得利益或者失去利益，当开除某个员工的时候，该员工的下属也必须开除；

分析：

给你两个整数n和m。

表示公司要开除n个员工，员工之间的关系有m个。

然后给你n个数字，可正可负。

表示开除这个员工所得到（正）或损失（负）的利益。

m 个关系 a b

表示b员工是a员工的下属。

闭合图定义：

它是有向图的一个点集，且这个点集的所有出边仍然指向该点集。

最大权闭合图：

每一个点有一个权值，可正可负，在所有的合法闭合图中，点权之和最大的图就是最大权闭合图。

明显，这道题目就是一个典型的最大权闭合图。

具体推理证明详见国家集训队论文：胡波涛的《最小割模型在信息学竞赛中的应用》

建图：

一个超级源点s，超级汇点t。

s连接所有点权为正的点，容量是点权。

所有点权为负的点连接汇点t，容量的点权乘以-1。

b 是 a的下属，那么连接 a b，容量无穷大。

求出最大流，那么所

有正点权的和 减去 最大流 就是最大权闭合图的最大权，就是公司的最大利益。

在残量网络中从原点s出发，一遍dfs，走还有容量的点，经过的点数就是要开除的人数。

略微证明一下：（证明转自：http://www.answeror.com/archives/27629）

1.因为不连接源汇的边的权值都是无穷大, 所以最小割一定是简单割（割边只和源点汇点有连接）, 最终被删除的点集即为去掉割以后源点s所在的集合, 记为S, 即若删除了v, 则v的所有后继都会被删除, 这就满足了原问题的唯一约束条件, 保证了解的正确性.

2.设正收益为b[i], 负收益的绝对值为c[i]. 对于任何一个负收益的顶点v[i]如果在S集合中, 说明v[i]要被删除, 此时容量c[i]被计算在切割中; 对于任何一个正收益的顶点v[i]如果在S集合中, 说明v[i]要被删除, 此时容量b[i]未被计算在切割中. 设正收益之和为B, 则B-sum{b[i]}+sum{c[j]}即为最小割的值(其中i为S中的所有正权点, j为S中的所有负权点), 等价于B-(sum{b[i]}-sum{c[j]}), 注意到括号内的值即为待求的总收益, 所以最小割对应了最大收益, 保证了解的最优性.

程序：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include"stdio.h"
#include"string.h"
#include"iostream"
#include"map"
#include"string"
#include"queue"
#include"stdlib.h"
#include"math.h"
#include"algorithm"
#include"vector"
#define M 9009
#define eps 1e-10
#define inf 1000000000000000
#define mod 1000000000
#define INF 1000000000
#define LL __int64
using namespace std;
struct node
{
    LL u,v,next,w;
}edge[M*50];
LL n,t,num,head[M],dis[M],p[M],q[M],use[M],work[M];
LL mini(LL a,LL b)
{
    return a<b?a:b;
}
void init()
{
    t=0;
    memset(head,-1,sizeof(head));
}
void add(LL u,LL v,LL w)
{
    edge[t].u=u;
    edge[t].v=v;
    edge[t].w=w;
    edge[t].next=head[u];
    head[u]=t++;
    edge[t].u=v;
    edge[t].v=u;
    edge[t].w=0;
    edge[t].next=head[v];
    head[v]=t++;
}
LL bfs(LL S,LL T)
{
    LL rear=0;
    memset(dis,-1,sizeof(dis));
    q[rear++]=S;
    dis[S]=0;
    for(LL i=0;i<rear;i++)
    {
        for(LL j=head[q[i]];j!=-1;j=edge[j].next)
        {
            LL v=edge[j].v;
            if(edge[j].w&&dis[v]==-1)
            {
                dis[v]=dis[q[i]]+1;
                q[rear++]=v;
                if(v==T)
                    return 1;
            }
        }
    }
    return 0;
}
LL dfs(LL S,LL a,LL T)
{
    if(S==T)return a;
    for(LL &i=work[S];i!=-1;i=edge[i].next)
    {
        LL v=edge[i].v;
        if(edge[i].w&&dis[v]==dis[S]+1)
        {
            LL tt=dfs(v,mini(a,edge[i].w),T);
            if(tt)
            {
                edge[i].w-=tt;
                edge[i^1].w+=tt;
                return tt;
            }
        }
    }
    return 0;
}
LL Dinic(LL S,LL T)
{
    LL ans=0;
    while(bfs(S,T))
    {
        memcpy(work,head,sizeof(head));
        while(LL tt=dfs(S,inf,T))
            ans+=tt;
    }
    return ans;
}
void DFS(LL u,LL f)
{
    use[u]=1;
    if(u!=0&&u!=n+1)
    num++;
    for(LL i=head[u];i!=-1;i=edge[i].next)
    {
        LL v=edge[i].v;
        if(edge[i].w&&!use[v])
        DFS(v,u);
    }
}
int main()
{
    LL m,i,a,b;
    while(scanf("%I64d%I64d",&n,&m)!=-1)
    {
        LL sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%I64d",&p[i]);
            if(p[i]>0)
                sum+=p[i];
        }
        init();
        for(i=1;i<=m;i++)
        {
            scanf("%I64d%I64d",&a,&b);
            add(a,b,inf);
        }
        for(i=1;i<=n;i++)
        {
            if(p[i]>0)
                add(0,i,p[i]);
            else
                add(i,n+1,-p[i]);
        }
        LL ans=Dinic(0,n+1);
        num=0;
        memset(use,0,sizeof(use));
        DFS(0,0);
        printf("%I64d %I64d
",num,sum-ans);
    }
    return 0;
}