记录编号	423897	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.929 s
提交时间	2017-07-12 17:37:41	内存使用	1.06 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define INF (0x7fffffff)
#define MAXN (65010)

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    register bool f = true;
    while(!isdigit(tmp) && tmp ^ '-') tmp = getc();
    if(tmp == '-') f = false, tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 48),
        tmp = getc();
    if(f) return res;
    return ~res + 1;
}

struct EDGE{ 
    int to, cap;
    EDGE *ne, *r;

    EDGE() { ;}
    EDGE(int _to, EDGE *_ne, int _cap) { 
        to = _to, ne = _ne, cap = _cap;
    }
};

inline void add_edge(int fr, int to, int cap);
inline bool Bfs(void);
int Dfs(int u, int min_flow);

EDGE *head[MAXN];
int N, M, S, T, tot, ans;
int bfn[MAXN];

int main() { 
#ifndef LOCAL
    freopen("profit.in", "r", stdin);
    freopen("profit.out", "w", stdout);
#endif
    N = read(), M = read();
    S = 0, T = M + N + 1;

    for(int i = 1; i <= N; ++i) add_edge(i, T, read());
    for(int i = N + 1, tmp; i < T; ++i) { 
        add_edge(i, read(), INF);
        add_edge(i, read(), INF);
        add_edge(S, i, tmp = read());
        tot += tmp;
    }

    int tmp;
    while(Bfs()) { 
        while((tmp = Dfs(S, INF))) ans += tmp;
    }

    printf("%d\n", tot - ans);
    return 0;
}

inline void add_edge(int fr, int to, int cap) { 
    head[fr] = new EDGE(to, head[fr], cap);
    head[to] = new EDGE(fr, head[to], 0);
    head[fr]->r = head[to]; head[to]->r = head[fr];
    return ;
}

inline bool Bfs(void) { 
    static int u, v;
    static queue<int> que;

    while(!que.empty()) que.pop();
    memset(bfn, 0x00, sizeof(bfn));

    que.push(S); bfn[S] = 1;

    while(!que.empty()) { 
        u = que.front();
        que.pop();
        if(u == T) return true;

        for(EDGE *e = head[u]; e; e = e->ne) { 
            if(!e->cap || bfn[v = e->to]) continue;
            bfn[v] = bfn[u] + 1;
            que.push(v);            
        }
    }
    return false;
}

int Dfs(int u, int min_flow) { 
    if(u == T) return min_flow;
    register int tmp, sum = 0, v;
    for(EDGE *e = head[u]; e; e = e->ne) { 
        if(e->cap && bfn[v = e->to] == bfn[u] + 1 && (tmp = Dfs(v, min(min_flow - sum, e->cap)))) { 
            e->cap -= tmp;
            e->r->cap += tmp;
            sum += tmp;
        }
    }
    return sum;
}