CF1082G Petya and Graph

题目描述

题目传送门

思路

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

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

先说做法：

新建原点 $s$ 与汇点 $t$ ；
将 $s$ 与图中每一个正权点相连，权值为该正权点点权；
将 $t$ 与图中每一个负权点相连，权值为该负权点点权的绝对值；
根据输入连边，边权为 $\infty$ 。

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

下面给出证明：

设集合 $S$ 和集合 $T$ 是原图的 $s-t$ 割。

记 $w$ 为当前的收益， $Cnt$ 为当前的割。

则 $w = S_\text{正权和} - |S_\text{负权和}|$ 。

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

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

移项得： $w = \text{正权和} - Cut$ 。

显然当 $Cut$ 取最小值（即最小割）时 $w$ 取最大值。

由最大流最小割定理得： $\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;
}