最大权闭合子图

发布于 2018-12-03  337 次阅读


题目链接

模型描述

有一个工厂,接到了 $n$ 个订单,为了完成这些订单,工厂需要采购一些机器,一共可采购 $m$ 台机器。我们知道完成每个订单的收益,也知道购买某个机器的开销。一个订单需要对应地购买某些机器,一台机器可以同时完成多个订单。现在工厂决定选择性地接一些订单,使得工厂的利润最大化。

解题报告

最大权闭合子图

我们来介绍一下什么是最大权闭合图。

闭合子图

定义一个有向图 $G(V,E)$ 的闭合子图为该有向图的一个子图 $G′(V′,E′)$ ,子图中每一个点的出边都指向这个子图里的点。例如下图就是一个闭合图。
闭合子图

最大权闭合子图

给每个顶点 $i$ 分配一个权值 $w_i$ ,最大权闭合子图就是点权总和 $\sum_{i∈V′} w_i$ 最大的闭合子图。
img
那么我们如何找到最大权闭合子图呢?
一般我们会将其转化为网络流模型。
具体来说:在原图的基础上新增加源点 $S$ 和汇点 $T$ ,原图所有边的流量设置为 $\text{INF}$ ,对于每一个边权为正的边,源点向其连一条流量为该点点权的边,对于每一个边权为负的边,这个点向汇点连一条流量为点权的绝对值的边。那么最大的权就是点权为正的点的点权和减去最小割,例如上图的例子可以转化为:
img
如何算方案呢?与源点相连的点都是最大权闭合子图的顶点。

证明

那么这个为什么是对的呢?我们尝试来证明它 $qwq$ 。

引理一:这个网络的最小割一定是一个简单割,也就是只会割直接与源点/汇点相连的边。

证明显然,没有与源点/汇点相连的边都是正无穷。

引理二:该图的每一个简单割产生的两个子图,我们记含有源点的图为 $S$ ,记含有汇点的图为 $T$ ,则图 $S$ 为闭合子图。

由于是简单割,所以 $S$ 中的任何一个节点都不能到达 $T$ ,所以该引理正确。

证明:最小割产生的图 $S$ 和 图 $T$ ,图 $S$ 为最大权闭合子图

因为割集中所有的边,不是连接到 $S$ 上,就是连接在 $T$ 上(引理一)。
我们记割边权值和为 $X$ ,割集中连接到源点的边的权值和为 $x_1$ ,连接到汇点的权值和为 $x_2$ ,则有 $X=x_1+x_2$ 。
记图 $S$ 的所有点的权值和为 $W$ ,记期中正权值之和为 $w_1$ ,负权值之和为 $−w2$ ,有 $W=w_1−w_2$ 。
所以有 $W+X=w_1−w_2+x_1+x_2$ 。
注意到 $x_2=w_2$ (图 $S$ 中点权为负的点一定一开始连接到汇点,后来被加入割集),可得 $W+X=w_1+x_1$ 。
显然 $w_1+x_1$ 是图中正点权权值和,记为 $SUM$ 。
因此 $W=SUM−X$ 。由引理二得知 $S$ 为一个闭合子图。$SUM$ 是一个定值,我们要使 $X$ 尽可能的小,也就是求最小割。

如何建模

我们把订单和机器都看成一些点,订单都为正边权,机器为负边权,订单指向这个订单需要的机器,显然这个图的最大权独立集就是答案(满足所有订单的最大收益方案)。

代码

(以链接里的题目代码为准,大同小异)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define RFOR(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000+5;

struct Node{
    struct Edge *first,*cur;
    int level;
}node[MAXN];

struct Edge{
    Node *s,*t;
    Edge *next,*rev;
    int cap,flow;
}pool[MAXN<<2],*frog = pool;

Edge *New(Node *s,Node *t,int cap){
    Edge *ret = ++frog;
    *ret = (Edge){s,t,s->first,NULL,cap,0};
    return ret;
}

inline void add(int u,int v,int cap,int rev=0){
    node[u].first = New(&node[u],&node[v],cap);
    node[v].first = New(&node[v],&node[u],rev);
    node[u].first->rev = node[v].first;
    node[v].first->rev = node[u].first;
}

int N,S,T;

bool bfs(Node *s,Node *t){
    FOR(i,0,N){
        node[i].cur = node[i].first;
        node[i].level = 0;
    }
    std::queue q;
    s->level = 1;q.push(s);
    while(!q.empty()){
        Node *v = q.front();q.pop();
        for(Edge *e = v->first;e;e = e->next){
            if(e->flow < e->cap && !e->t->level){
                e->t->level = v->level + 1;
                if(e->t == t) return true;
                q.push(e->t);
            }
        }
    }
    return false;
}

int dfs(Node *v,Node *t,int limit = INT_MAX){
    if(v == t) return limit;
    int flow;
    for(Edge *&e = v->cur;e;e = e->next){
        if(e->flow < e->cap && e->t->level == v->level + 1){
            if((flow = dfs(e->t,t,std::min(limit,e->cap-e->flow)))){
                e->flow += flow;
                e->rev->flow -= flow;
                return flow;
            }
        }
    }
    return 0;
}

int dinic(){
    int ans=0,flow;
    while(bfs(&node[S],&node[T])){
        while((flow = dfs(&node[S],&node[T]))){
            ans += flow;
        }
    }
    return ans;
}

int n,m,sum;

int main(){
    scanf("%d%d",&n,&m);
    N = n+m+1;
    S = 0,T = N;
    FOR(i,1,m){
        int x;scanf("%d",&x);
        add(i+n,T,x);
    }
    FOR(i,1,n){
        int a,k;
        scanf("%d%d",&a,&k);
        sum += a;add(S,i,a);
        FOR(j,1,k){
            int x;scanf("%d",&x);
            add(i,x+n,INT_MAX);
        }
    }
    printf("%d\n",sum-dinic());
    // system("pause");
    return 0;
}

一个OIer。