题目地址：洛谷：【P4174】[NOI2006]最大获利 – 洛谷、BZOJ：Problem 1497. — [NOI2006]最大获利

题目描述

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。
在前期市场调查和站址勘测之后，公司得到了一共 N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 i个通讯中转站需要的成本为 Pi（1≤i≤N）。
另外公司调查得出了所有期望中的用户群，一共 M 个。关于第 i 个用户群的信息概括为 Ai, Bi和 Ci：这些用户会使用中转站 Ai 和中转站 Bi 进行通讯，公司可以获益 Ci。（1≤i≤M, 1≤Ai,Bi≤N）
THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

输入输出格式

输入格式：
输入文件中第一行有两个正整数 N 和 M 。
第二行中有 N 个整数描述每一个通讯中转站的建立成本，依次为 P1,P2,…,PN。
以下 M 行，第(i + 2)行的三个数 Ai,Bi和 Ci描述第 i 个用户群的信息。
所有变量的含义可以参见题目描述。

输出格式：
你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

输入输出样例

输入样例#1：

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

输出样例#1：

4

说明

样例：选择建立 1、2、3 号中转站，则需要投入成本 6，获利为 10，因此得到最大收益 4。
100%的数据中：N≤5 000，M≤50 000，0≤ Ci ≤100，0≤ Pi ≤100。

题解

这类问题有一个统一的模型，叫最大权闭合子图。
我们把中转站向汇连边，容量为建设成本。把客户向源连边，容量为获利。再把客户和用到的中转站之间连边，容量无限。求一次最小割，然后用所有获利减去这个最小割的权值和即为答案。
最小割肯定不会去割中间容量无限的边，因此割的是与源汇相连的边。割掉客户与源相连的边的含义是不要这个客户了，割掉中转站与汇相连的边的含义是不建这个中转站了。因此最小割的含义是发展客户净利润为负的收益加上建设中转站的总成本，也就是损失的收益+建设的开支，直接用总收益减去它就是答案。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 3];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(level[v] == -1 && gra[i].cap > 0) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || left <= 0) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                left -= d; flow += d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(left <= 0) {
                    //level[u] = -1; 不注释掉会TLE
                    return flow;
                }
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

int n, m, pi, ai, bi, ci, S, T, ans;

// 1 ~ n device
// n+1 ~ n+m custom

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    S = n + m + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        pi = readint();
        addedge(i, T, pi);
    }
    for(int i = 1; i <= m; i++) {
        ai = readint(); bi = readint(); ci = readint();
        ans += ci;
        addedge(S, n + i, ci);
        addedge(n + i, ai, INF);
        addedge(n + i, bi, INF);
    }
    ans -= dinic(S, T);
    printf("%d", ans);
    return 0;
}