POJ 2987 最大权闭合图

请参考胡伯涛的论文《最小割模型在信息学竞赛中的应用》

闭合图的概念就很好引出了。在一个图中，我们选取一些点构成集合，记为V，且集合中的出边(即集合中的点的向外连出的弧)，所指向的终点(弧头)也在V中，则我们称V为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。

首先引入结论，最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图，接下来我们来说明一些结论。

证明:最小割为简单割。

引入一下简单割的概念：割集的每条边都与S或T关联。(请下面阅读时一定分清最小割与简单割，容易混淆)

那么为什么最小割是简单割呢？因为除S和T之外的点间的边的容量是正无穷，最小割的容量不可能为正无穷。所以，得证。

证明网络中的简单割与原图中闭合图存在一一对应的关系。(即所有闭合图都是简单割，简单割也必定是一个闭合图)。

证明闭合图是简单割：如果闭合图不是简单割(反证法)。那么说明有一条边是容量为正无穷的边，则说明闭合图中有一条出边的终点不在闭合图中，矛盾。

证明简单割是闭合图：因为简单割不含正无穷的边，所以不含有连向另一个集合(除T)的点，所以其出边的终点都在简单割中，满足闭合图定义。得正。

证明最小割所产生的两个集合中，其源点S所在集合(除去S)为最大权闭合图。

首先我们记一个简单割的容量为C,且S所在集合为N，T所在集合为M。

则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解，不理解画一个图或想象一下就明白了)。

我们记N这个闭合图的权值和为W。

则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2);

则W+C=x1+y1+x2-y2。

因为明显y1=y2，所以W+C=x1+x2;

x1为M中所有权值为正的点的权值，x2为N中权值为正的点的权值。

所以x1+x2=所有权值为正的点的权值之和(记为TOT).

所以我们得到W+C=TOT.整理一下W=TOT-C.

到这里我们就得到了闭合图的权值与简单割的容量的关系。

因为TOT为定值，所以我们欲使W最大，即C最小，即此时这个简单割为最小割，此时闭合图为其源点S所在集合(除去S)。得正。

至此，我们就将最大权闭合图问题转化为了求最小割的问题。求最小割用最小割容量=最大流，即可将问题转化为求最大流的问题。

-----------------------------------------------------------

然后再说本题

本题还有一个要求就是要求不仅要是最大权，并且要求点数还最少

看一个神牛的证明----http://hi.baidu.com/dispossessed/blog/item/2396c0ddbc73a2caa044df44.html

下面证明最小割对应取点方案就是最小取点数

由于原图是个DAG图，所以对于取得的最大权闭合图K，取它的任意一个子图G，如果从K-G仍然是一个闭合图，那么的点权和一定大于等于0，例如：1->2,2->3,1->4,4->5，若最大权闭合图为：{1,2,3,4,5}，那么其中任一满足条件的G（{1},{1,2},{1,2,3},{1,4},{1,4,5})点权和一定大于等于0，否则去除G，K-G仍然为闭合图，但是K-G的点权和会大于K

所以如果有两种取点方式使得权值相同，但是取点数不同的话，那么肯定存在一个可以移除的满足条件的子图G，其点权和为0

下面考虑构造的网络，对于G在网络中的对应图G'，由于在网络求的是最小割，即最大流，而且G的点权和为0，所以G'中与源点S连边的容量和等于G'中与汇点T连边的流量和，同时由于去除G后K还是一个闭合图，所以只有可能G'中的流量流入K'-G'，不可能有流量从K'-G'流入G'，所以G'的边中除了流量为inf的那些，一定是满流的

再考虑在残留网络中求出取点集的方法，从源点开始floodfill，忽略满流边，即残留网络中的0流边，可以遍历到的点就是要取的点集了，这个道理想一下简单割和闭合图的取法一一对应就可以了

那么G'既然是满流的，在残留网络中就不可能对这些0流边进行处理，那就不会取到G中的点进入取点集，所以建立网络求得得最小割对应的取法取出的就是最小的点数了

--------------------------------

当然还有一种是神奇的放大边权方法

建图前，对所有b[i]，执行变换b[i]=b[i]*10000-1，然后，会惊异地发现，
此时最大流所对应的方案就是满足辞退最少人数的了。
为什么？显然，变换后的流量r2除以10000后再取整就等于原来的流量，但是
r2的后四位却蕴含了辞退人数的信息：每多辞退一个人，流量就会少1。

上代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define MAXN 5555
#define MAXM 555555
#define INF 1000000007
using namespace std;
struct node
{
    int ver;    // vertex
    int cap;    // capacity
    int flow;   // current flow in this arc
    int next, rev;
}edge[MAXM];
int dist[MAXN], numbs[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, int c)
{       //e记录边的总数
    edge[e].ver = y;
    edge[e].cap = c;
    edge[e].flow = 0;
    edge[e].rev = e + 1;        //反向边在edge中的下标位置
    edge[e].next = head[x];   //记录以x为起点的上一条边在edge中的下标位置
    head[x] = e++;           //以x为起点的边的位置
    //反向边
    edge[e].ver = x;
    edge[e].cap = 0;  //反向边的初始容量为0
    edge[e].flow = 0;
    edge[e].rev = e - 1;
    edge[e].next = head[y];
    head[y] = e++;
}
void rev_BFS()
{
    int Q[MAXN], qhead = 0, qtail = 0;
    for(int i = 1; i <= n; ++i)
    {
        dist[i] = MAXN;
        numbs[i] = 0;
    }
    Q[qtail++] = des;
    dist[des] = 0;
    numbs[0] = 1;
    while(qhead != qtail)
    {
        int v = Q[qhead++];
        for(int i = head[v]; i != -1; i = edge[i].next)
        {
            if(edge[edge[i].rev].cap == 0 || dist[edge[i].ver] < MAXN)continue;
            dist[edge[i].ver] = dist[v] + 1;
            ++numbs[dist[edge[i].ver]];
            Q[qtail++] = edge[i].ver;
        }
    }
}
void init()
{
    e = 0;
    memset(head, -1, sizeof(head));
}
long long maxflow()
{
    int u;
    long long totalflow = 0;
    int Curhead[MAXN], revpath[MAXN];
    for(int i = 1; i <= n; ++i)Curhead[i] = head[i];
    u = src;
    while(dist[src] < n)
    {
        if(u == des)     // find an augmenting path
        {
            int augflow = INF;
            for(int i = src; i != des; i = edge[Curhead[i]].ver)
                augflow = min(augflow, edge[Curhead[i]].cap);
            for(int i = src; i != des; i = edge[Curhead[i]].ver)
            {
                edge[Curhead[i]].cap -= augflow;
                edge[edge[Curhead[i]].rev].cap += augflow;
                edge[Curhead[i]].flow += augflow;
                edge[edge[Curhead[i]].rev].flow -= augflow;
            }
            totalflow += augflow;
            u = src;
        }
        int i;
        for(i = Curhead[u]; i != -1; i = edge[i].next)
            if(edge[i].cap > 0 && dist[u] == dist[edge[i].ver] + 1)break;
        if(i != -1)     // find an admissible arc, then Advance
        {
            Curhead[u] = i;
            revpath[edge[i].ver] = edge[i].rev;
            u = edge[i].ver;
        }
        else        // no admissible arc, then relabel this vertex
        {
            if(0 == (--numbs[dist[u]]))break;    // GAP cut, Important!
            Curhead[u] = head[u];
            int mindist = n;
            for(int j = head[u]; j != -1; j = edge[j].next)
                if(edge[j].cap > 0)mindist = min(mindist, dist[edge[j].ver]);
            dist[u] = mindist + 1;
            ++numbs[dist[u]];
            if(u != src)
                u = edge[revpath[u]].ver;    // Backtrack
        }
    }
    return totalflow;
}
int nt, m;
int vis[MAXN];
void dfs(int u)
{
    if(u == des) return;
    vis[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].next)
        if(edge[i].cap > 0 && !vis[edge[i].ver])
            dfs(edge[i].ver);
}
int main()
{
    init();
    scanf("%d%d", &nt, &m);
    src = nt + 1;
    des = nt + 2;
    n = des;
    long long sum = 0;
    int w, u, v;
    for(int i = 1; i <= nt; i++)
    {
        scanf("%d", &w);
        if(w > 0)
        {
            sum += w;
            add(src, i, w);
        }
        else if(w < 0)  add(i, des, -w);
    }
    while(m--)
    {
        scanf("%d%d", &u, &v);
        add(u, v, INF);
    }
    rev_BFS();
    long long flow = maxflow();
    memset(vis, 0, sizeof(vis));
    dfs(src);
    int ans = 0;
    for(int i = 1; i <= nt; i++)
        if(vis[i]) ans++;
    printf("%d %I64d\n", ans, sum - flow);
    return 0;
}