$网络流算法$、$网络流⋅最大流$ 、 $网络流⋅最小割$

$$\huge 最大权闭合子图$$

$问题描述$

$在一张有向无权图G = (V,E)中,每个点有一个点权w_u(可能为负数)$

$选择一个点集S,使得任何起点位 u 边(u,v),若u \in S,那么v \in S $

$子图S的权值为\sum_{u\in S}w_u$

$求权值最大子图的权值$

$建图$

$对于原图G的一条边,其权值为inf$

$建立新的原点S以及新的汇点T$

$对于点权大于0的点v,从S向v连权值为W_v的边$

$否则从v向T连权值为$-$W_v的边$

$定理$

$权值最大子图的权 = \sum_{v\in V}W_v - G’的最小割$

$简单割$

$把图分成S和T两部分后,所有割边(u,v)都不能使得 u\in V 且 v \in V$

$由于已经把内部边设成了inf,所以最小割一定是简单割$

$证明$

对应关系

$闭合子图 <=> 简单割$

$设P = 闭合子图,若{(u,v)\in E, u\in P},那么v \in ${$ P,T $}

$S = P + ${$s$}$ , T = V - S, 即一个简单割$

$简单割[S,T],P = S - ${$s$},$若(u,v)\in E, u\in P, 那么v \in ${$P,T$}

$即一个闭合子图$

数量关系

$简单割[S,T],V_1 = S - ${$s$}$, V_2 = T - ${$t$}

$X^- 表示X中点权小于等于0的点，X^+ 表示X中点权大于0的点$

$C[S,T] = C[V_1,${$t$}$] + C[${$s$}$,V_2]$

$\ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{v\in V_1^-}($-$W_v) + \sum_{v\in V_2^+}(W_v)$

$闭合子图权值 = \sum_{v\in V_1^+}(W_v) + \sum_{v\in V_1^-} (W_v)$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{v\in V_1^+}(W_v) - \sum_{v\in V_1^-} ($-$W_v)$

$C[S,T] + W(P) = \sum_{v\in V}W_v$

$W(P) = \sum_{v\in V}W_v - C[S,T]$

$C[S,T]尽量小,才能让W(P)尽量大$

$即权值最大子图的权 = \sum_{v\in V}W_v - G’的最小割$

$证毕$

$Code$

#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;
}