最大权闭合子图

一、概念

闭合子图

给定一个有向图\(G(V,E)\)，图中的某一个点集，这个点集满足内部的所有边不能从点集里面指向点集外面，则将这个点集和点集里面的边统称为原图的闭合子图

最大权闭合子图

给定一个有向图\(G(V,E)\)，每个点上有一个权值，图中存在若干个闭合子图，若其中一个闭合子图的点集权值和最大，则这个闭合子图称为最大权闭合子图

简单割

割边都与源点或汇点相连的割（概念只针对于本篇问题）

二、算法流程

建图

新建一个源点\(S\)和汇点\(T\)，从源点\(S\)向\(w_i>0\)的点连一条边权为\(w_i\)的边，从所有\(w_i<0\)的点向汇点\(T\)连一条边权为\(-w_i\)的边，原图中点与点之间的边不变，流量设为\(+\infty\)

计算

对新图求一遍最小割，最大权\(=\sum_{w_i>0}w_i-\)最小割

三、算法证明

证明新图中的最小割是简单割

\(Proof\)

最小割\(=\)最大流，且新图中最大流是有限的
\(\Rightarrow\)最小割的割边必然不会包含图中\(+\infty\)的边
\(\Rightarrow\)割边都与源点或汇点相连
\(\Rightarrow\)最小割是简单割

证明原图中闭合子图和新图中的简单割一一对应

\(Proof\)

闭合子图\(\rightarrow\)简单割

新图的点集记为\(V\),对原图中的一个闭合子图，点集记为\(V'\)

构造割集\([S,T]\),其中\(S=V'+\{s\}\), \(T=V-S\)

由闭合子图的定义，\(S\)中除\(s\)外的点不存在边与\(T\)中除\(t\)外的点相连

因此割边都与源点或汇点相连

所以构造的割是简单割

简单割\(\rightarrow\)闭合子图

对于一个简单割\([S,T]\),构造闭合子图\(G(V,E)\)，其中\(V=S-\{s\}\)

由于简单割保证了两个集合之间不存在相连的边，所以从\(S\)的任何一个点出发，都必然会走回到\(S\)，不可能走到\(T\)

因此\(V\)是一个闭合点集，\(G\)是一个闭合子图

证明最大权\(=\sum_{w_i>0}w_i-\)最小割

\(Proof\)

对任意一个简单割\([S,T]\)，记对应的闭合子图点集\(V_1=S-\{s\}\),记\(V_2=V-V_1\)

\(X^+\)表示\(X\)中权值为正的点，\(X^-\)表示\(X\)中权值为负的点

则简单割的容量\(c[S,T]=\sum_{u{\in}V_2^+}w_u+\sum_{u{\in}V_1^-}(-w_u)\)

闭合子图的权值和 \(W=\sum_{u{\in}V_1^+}w_u-\sum_{u{\in}V_1^-}(-w_u)\)

两式相加得 \(W+c[S,T]=\sum_{u{\in}V^+}w_u\)

即 \(W=\sum_{u{\in}V^+}w_u-c[S,T]\)

\(\sum_{u{\in}V^+}w_u\)固定不变，要使\(W\)最大，就是要\(c[S,T]\)最小，因此\([S,T]\)为最小割

四、示例代码

#include <bits/stdc++.h>

using namespace std;

const int N = 55010, M = 310010, inf = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], c[M], ne[M], idx;
int q[N], dep[N], cur[N];

void add(int u, int v, int w)
{
    e[idx] = v, c[idx] = w, ne[idx] = h[u], h[u] = idx ++ ;
    e[idx] = u, c[idx] = 0, ne[idx] = h[v], h[v] = idx ++ ;
}

bool bfs()
{
    memset(dep, -1, sizeof dep);
    int hh = 0, tt = 0;
    q[0] = S, dep[S] = 0;
    cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dep[j] == -1 && c[i])
            {
                dep[j] = dep[t] + 1;//建立分层图
                cur[j] = h[j];
                if (j == T)return true;
                q[++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)//寻找增广路
{
    if (u == T)return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;//当前弧优化
        int j = e[i];
        if (dep[j] == dep[u] + 1 && c[i])
        {
            int t = find(j, min(c[i], limit - flow));
            if (!t)dep[j] = -1;//费点优化
            c[i] -= t, c[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while (bfs()) while (flow = find(S, inf))res += flow;
    return res;
}

int init()
{
    int t = 0;
    scanf("%d%d", &n, &m);
    S = 0, T = n + m + 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int p;
        scanf("%d", &p);
        add(i, T, p);
    }
    for (int i = n + 1; i <= n + m; i ++ )
    {
        int a, b, cc;
        scanf("%d%d%d", &a, &b, &cc);
        add(i, a, inf), add(i, b, inf), add(S, i, cc);
        t += cc;
    }
    return t;
}

int main()
{
    printf("%d", init() - dinic());
    return 0;
}

参考文献

https://www.acwing.com/file_system/file/content/whole/index/content/6250083/

https://blog.csdn.net/qq_41730082/article/details/104526447