Description

新的技术正冲击着手机通讯市场, 对于各大运营商来说, 这既是机遇, 更是挑战. THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜, 需要做太多的准备工作, 仅就站址选择一项, 就需要完成前期市场研究、站址勘测、最优化等项目.

在前期市场调查和站址勘测之后, 公司得到了一共 \(n\) 个可以作为通讯信号中转站的地址, 而由于这些地址的地理位置差异, 在不同的地方建造通讯中转站需要投入的成本也是不一样的, 所幸在前期调查之后这些都是已知数据: 建立第 \(i\) 个通讯中转站需要的成本为 \(P_i (1 \leq i \leq N)\).

另外公司调查得出了所有期望中的用户群, 一共 \(m\) 个. 关于第 \(i\) 个用户群的信息概括为 \(A_i, B_i\) 和 \(C_i\): 这些用户会使用中转站 \(A_i\) 和中转站 \(B_i\) 进行通讯, 公司可以获益 \(C_i\).

THU 集团的 CS&T 公司可以有选择的建立一些中转站 (投入成本), 为一些用户提供服务并获得收益 (获益之和). 那么如何选择最终建立的中转站才能让公司的净获利最大呢? (净获利=获益之和 – 投入成本之和)

Input

输入文件中第一行有两个正整数 \(n\) 和 \(m\).

第二行中有 \(n\) 个整数描述每一个通讯中转站的建立成本, 依次为 \(P_1, P_2, \ldots, P_n\).

以下 \(m\) 行, 第 \(i+2\) 行的三个数 \(A_i, B_i, C_i\) 描述第 \(i\) 个用户群的信息.

所有变量的含义可以参见题目描述.

Output

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

Sample Input

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

Sample Output

4

Data Range

80% 的数据中:\(n \leq 200, m \leq 1000\);

100% 的数据中:\(n \leq 5000, m \leq 50000, 0 \leq C_i \leq 100, 0 \leq P_i \leq 100\).

Explanation

先考虑全部获利, 然后再断开最少的链路. 最小割上总结点数为 \(n+m+2\), 然后读者就可以自行脑补了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 60010, maxm = 500100;
const int infinit = 1000000000;//0x3fffffff;

class Dinic
{
public:
    struct edge
    {
        int u, v, flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, int flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        memset(level, 0, sizeof(level));
        queue<int> que;
        que.push(s); level[s] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] <= 0)
            return false;
        return true;
    }
    int find(int p, int mn)
    {
        if (p == t)
            return mn;
        int sum = 0, tmp;
        for (edge *ep = edges[p]; sum < mn && ep; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = find(ep->v, min(ep->flow, mn - sum));
                if (tmp > 0) {
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                    sum += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    int eval(void)
    {
        int sum = 0, tmp;
        while (make_level()) {
            tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    graph.n = n + m + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    int res = 0; // The total, from which has to be cut
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        graph.add_edge(i + m, graph.t, x);
    }
    for (int i = 1, x, y, z; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        res += z;
        graph.add_edge(graph.s, i, z);
        graph.add_edge(i, x + m, infinit);
        graph.add_edge(i, y + m, infinit);
    }
    // Evaluate minimum cut
    res -= graph.eval();
    printf("%d\n", res);
    return 0;
}