题目描述

题目传送门

思路

这道题和 [NOI2006] 最大获利 是一模一样的,做完记得去拿双倍经验

这道题是一个经典的网络流模型:最大权闭合子图

先说做法:

  1. 新建原点 ss 与汇点 tt

  2. ss 与图中每一个正权点相连,权值为该正权点点权;

  3. tt 与图中每一个负权点相连,权值为该负权点点权的绝对值;

  4. 根据输入连边,边权为 \infty

最后,答案为正权点和 - 最大流。

下面给出证明:

设集合 SS 和集合 TT 是原图的 sts-t 割。

ww 为当前的收益 , CntCnt 为当前的割。

w=S正权和S负权和w = S_\text{正权和} - |S_\text{负权和}|

显然 Cut=正权和S正权和+S负权和Cut = \text{正权和} - S_\text{正权和} + |S_\text{负权和}|

加起来就有:w+Cut=正权和w + Cut = \text{正权和}

移项得:w=正权和Cutw = \text{正权和} - Cut

显然当 CutCut 取最小值(即最小割)时 ww 取最大值。

由最大流最小割定理得:maxw=正权和最大流\max_w = \text{正权和} - \text{最大流}

证必。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 50010 , MAXM = 500010 , INF = 1 << 30;

int N , M;

int Head[MAXN * 4];
int Cnt = 1;
struct Edge {
    int Next , To;
    int Val;
} G[MAXM * 15];

void _add(int u , int v , int w) {
    G[++Cnt].To = v;
    G[Cnt].Val = w;
    G[Cnt].Next = Head[u];
    Head[u] = Cnt;
}

void Add(int a , int b , int c) {
    _add(a , b , c);
    _add(b , a , 0);
}

int Dep[MAXN * 4];
int Hash[MAXN * 4];

int S , T;
int Max_Flow;

void Bfs() {
    memset(Dep , -1 , sizeof Dep);
    memset(Hash , 0 , sizeof Hash);
    queue<int> q;
    q.push(T);
    Dep[T] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = Head[u]; i; i = G[i].Next) {
            int v = G[i].To;
            if(Dep[v] != -1) continue;
            q.push(v);
            Dep[v] = Dep[u] + 1;
            Hash[Dep[v]]++;
        }
    }
}

int Dfs(int u , int flow) {
    if(u == T) {
        Max_Flow += flow;
        return flow;
    }
    int used = 0;
    for(int i = Head[u]; i; i = G[i].Next) {
        int v = G[i].To;
        if(G[i].Val && Dep[v] + 1 == Dep[u]) {
            int Min = Dfs(v , min(flow - used , G[i].Val));
            if(Min) {
                G[i].Val -= Min;
                G[i ^ 1].Val += Min;
                used += Min;
            }
            if(used == flow) {
                return used;
            }
        }
    }
    Hash[Dep[u]]--;
    if(Hash[Dep[u]] == 0) Dep[S] = N + M + 10;
    Dep[u]++;
    Hash[Dep[u]]++;
    return used;
}

int ISAP() {
    Max_Flow = 0;
    Bfs();
    while(Dep[S] < N + M + 10) Dfs(S , INF);
    return Max_Flow;
}

int Sum;

signed main() {
    scanf("%lld%lld" ,&N ,&M);

    S = 0;
    T = N + M + 1;

    for(int i = 1 , k; i <= N; i++) {
        scanf("%lld" ,&k);
        Add(i + M , T , k);
    }

    for(int i = 1 , u , v , w; i <= M; i++) {
        scanf("%lld%lld%lld" ,&u ,&v ,&w);
        Sum += w;
        Add(S , i , w);
        Add(i , M + u , INF);
        Add(i , M + v , INF);
    }

    printf("%lld\n" ,Sum - ISAP());

    return 0;
}