记录编号	431897	评测结果	AAAAAAAAAA
题目名称	28.[NOI 2006]最大获利	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.117 s
提交时间	2017-08-02 10:15:38	内存使用	1.14 MiB

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define INF 0x7fffffff
#define MAXN 60000
namespace IO {
	char buf[1 << 15], *fs, *ft;
	inline char gc() { return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 15, stdin), fs == ft)) ? 0 : *fs++; }
	inline int qr() {
		int x = 0, ch = gc();
		while (ch<'0' || ch>'9') { ch = gc(); }
		while (ch >= '0'&&ch <= '9') { x = (x << 1) + (x << 3) + ch - '0';ch = gc(); }
		return x;
	}
}using namespace IO;
using namespace std;
/***********************************************************************************************/
struct Edge {
	int t, next, v;
}e[400000];
int N, M, S, T, head[MAXN], cnt = 1, cur[MAXN], dis[MAXN];
void Add_Edge(int from, int to, int cap) {
	e[++cnt].t = to;e[cnt].next = head[from];head[from] = cnt;e[cnt].v = cap;
	e[++cnt].t = from;e[cnt].next = head[to];head[to] = cnt;e[cnt].v = 0;
}
bool BFS() {
	memset(dis, -1, sizeof(dis));
	queue<int>q;
	q.push(S);dis[S] = 0;
	while(!q.empty()){
		int u = q.front();q.pop();
		for (int i = head[u];i != -1;i = e[i].next) {
			if (e[i].v > 0 && dis[e[i].t] == -1) {
				dis[e[i].t] = dis[u] + 1;q.push(e[i].t);
			}
		}
	}
	if (dis[T] == -1)return 0;
	return 1;
}
int DFS(int u, int now) {
	if (u == T)return now;
	int f, flow = 0;
	for (int &i = cur[u];i != -1;i = e[i].next) {
		if (e[i].v > 0 && dis[e[i].t] == dis[u] + 1 && (f = DFS(e[i].t, min(e[i].v, now - flow)))) {
			e[i].v -= f;e[i ^ 1].v += f;flow += f;
			if (flow == now)return flow;
		}
	}
	if (!flow)dis[u] = -1;
	return flow;
}
int x, y, z, ans;
int sb() {
	freopen("profit.in", "r", stdin);
	freopen("profit.out", "w", stdout);
	memset(head, -1, sizeof(head));
	N = qr();M = qr();
	S = 0;T = N + M + 1;
	for (int i = 1;i <= N;i++) {
		x = qr();
		Add_Edge(i, T, x);
	}
	for (int i = 1;i <= M;i++) {
		x = qr();y = qr();z = qr();
		ans += z;
		Add_Edge(S, i + N, z);
		Add_Edge(i + N, x, INF);
		Add_Edge(i + N, y, INF);
	}
	while (BFS()) {
		memcpy(cur, head, sizeof(head));
		ans -= DFS(S, INF);
	}
	printf("%d", ans);
	return 0;
}
int chh = sb();
int main() { ; }