POJ 2987 Firing 题解【网络流】【最大权闭合子图】

点击量：284

需要证明一个结论。然后灵活运用最大权闭合子图。

目录

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\le 5000)$ and $ m$ $ (0\le m\le 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 $ b_i$ $ (|b_i|\le 10^7, 1\le i\le n)$. The remaining $ m$ lines each contain two integers $ i$ and $ j$ $ (1\le i,j\le 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.

Source

POJ Monthly–2006.08.27, frkstyc

题意：

现在公司需要裁员，有一些员工之间存在着一些连带关系。比如说，员工$ A,B$之间有连带关系，如果解雇了$ A$，那么$ B$也会被解雇。这种关系是单向的。

现在解雇每个员工都会产生一定收益或损失，现在要你求出最大收益，并输出最大收益时裁员的最小数目。

题解：

最大收益比较好求，直接建立网络流求出最大权闭合子图即可。关键是裁员的最小数目。

当我们做完第一问时，会产生一个残量网络，这时从源点dfs到的点就是最大权闭合子图上的点。如果头铁直接输出了这个点数，可以得到AC。但是这一结论可以被证明吗？为什么这样求出来的点数最小呢？

不妨设该网络流图存在两个最大权闭合子图$ S_1,S_2​$。当$ S_1\cap S_2=\varnothing​$时，$ S_1\cup S_2​$一定也是个闭合图，此时点数一定比原来大，因此不会出现这种情况。

当$ S_1\cap S_2\ne\varnothing$时，反设$ |S_1|<|S_2|$，若$ S_1\subset S_2$，则$ \exists \langle u,v\rangle,u\in S_1,v\in(S_2-S_1)$，不满足$ S_1$是闭合图。因此无法满足包含关系。则一定有$ |S_1|=|S_2|$。设$ S_1\cap S_2=F$，则$ S_1$与$ S_2$不同的地方就在于$ S_1-F$和$ S_2-F$。

所以当$ \exists \langle u,v\rangle,u\in F,v\in S_1-F$时，$ S_2$就不是闭合图了，因为$ F\subset S_2$有边连到$ S_2$外面去了。

当$ \nexists\langle u,v\rangle,u\in F,v\in S_1-F$时，$ F$没有边连向$ S_1-F$，此时$ S_1\cup S_2$也是闭合图。当$ S_1-F$的权值和为$ 0$时，dfs不会找到这一区域，因为源点连过来的边容量为$ 0$，对答案没有影响。当$ S_1-F$的权值和大于$ 0$时，第一问的答案就要改变了。

$ S_2-F$同理。

针对以上两种情况的解释：

该证明一定程度上借鉴了https://blog.csdn.net/scorpiocj/article/details/6085637。不过感觉这里更直观一些吧。

输出的时候第一问放在后面。并且利益要用long long存。

Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[150000];
int head[5050],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],0);
    head[to]=ecnt;
}
int d[5050],q[5050];
bool bfs()
{
    int l=0,r=0;
    memset(d,0,sizeof(d));
    q[++r]=5001;
    d[5001]=1;
    while(l<r)
    {
        int x=q[++l];
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i^1].v&&!d[e[i].n])
            {
                d[e[i].n]=d[x]+1;
                q[++r]=e[i].n;
            }
    }
    return d[0]>0;
}
int dinic(int x,int in)
{
    if(x==5001)
        return in;
    int flow=in;
    for(int i=head[x];flow&&~i;i=e[i].nxt)
        if(e[i].v&&d[e[i].n]==d[x]-1)
        {
            int tmp=dinic(e[i].n,Min(e[i].v,flow));
            if(!tmp)
                d[e[i].n]=0;
            e[i].v-=tmp;
            e[i^1].v+=tmp;
            flow-=tmp;
        }
    return in-flow;
}
long long ans=0,cnt=-1;
bool used[5050];
void dfs(int x)
{
    ++cnt;
    used[x]=1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].v&&!used[e[i].n])
            dfs(e[i].n);
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&u);
        if(u<0)
            add(i,5001,-u);
        else
        {
            add(0,i,u);
            ans+=u;
        }
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        add(u,v,0x3fffffff);
    }
    while(bfs())
    {
        int tmp=dinic(0,0x3fffffff);
        while(tmp)
        {
            ans-=tmp;
            tmp=dinic(0,0x3fffffff);
        }
    }
    dfs(0);
    printf("%lld %lld\n",cnt,ans);
    return 0;
}