Description
你去找某 bm 玩，到了门口才发现要打开他家的大门不是一件容易的事……
他家的大门外有 (n) 个站台，用 (1) 到 (n) 的正整数编号。你需要对每个站台访问一定次数以后大门才能开启。站台之间有 (m) 个单向的传送门，通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门，你就需要乘坐公共汽车，并花费 (1) 单位的钱。值得庆幸的是，任意两个站台之间都有公共汽车直达。
现在给你每个站台必须访问的次数 (F_i) ，对于站台 (i) ，你必须恰好访问 (F_i) 次（不能超过）。
我们用 (u) 、 (v) 、 (w) 三个参数描述一个传送门，表示从站台 (u) 到站台 (v) 有一个最多可以使用 (w) 次的传送门（不一定要使用 (w) 次）。值得注意的是，对于任意一对传送门 ((u_1,v_1)) 和
((u_2,v_2)) ，如果有 (u_1<u_2) ，则有 (v_1le v_2) ；如果有 (v_1<v_2) ，则有 (u_1le u_2) ；且 (u_1=u_2) 和 (v_1=v_2) 不同时成立。
你可以从任意的站台开始，从任意的站台结束。出发去开始的站台需要花费 (1) 单位的钱。你需要求出打开大门最少需要花费多少单位的钱。
Input
第一行包含两个正整数 (n) 、 (m) ，意义见题目描述。第二行包含 (n) 个正整数，第 (i) 个数表示 (F_i) 。接下来有 (m) 行，每行有三个正整数 (u) 、 (v) 、 (w) ，表示从 (u) 到 (v) 有一个可以使用 (w) 次的传送门。
Output
输出一行一个整数，表示打开大门最少花费的钱数。
Sample Input
4 3
5 5 5 5
1 2 1
3 2 1
3 4 1
Sample Output
17
HINT
(100\%) 的数据满足 (1le nle 10000) ， (1≤m≤100000) ；
对于所有的 (u) 、(v) ，满足 (1≤u,v≤n) ，(u≠v) ；对于所有的 (w) 、(F_i) ，满足 (1≤w,Fi≤50000) 。
以上的每类数据中都存在 (50\%) 的数据满足对于所有的 (w) 、(F_i) ，有 (w=F_i=1) 。
Soution
最开始想的是要把每个公交车都体现在图上，发现会有 (n^2) 条边，跪了。
想了想，可以把问题转换为最多使用多少次传送门，这样就可以把公交车的连边问题略去了。
考虑拆点。点 (x) 拆成 (x_1) 和 (x_2) 。考虑连边 $$<S, x_1>:capacity=F[x]$$ $$<x_2,T>:capacity=F[x]$$ $$<x_1,y_2>:capacity=w$$
最后答案就是 $$sum_{i=1}^nF[i] - maxFlow$$
#include<bits/stdc++.h>
using namespace std;
#define N 20001
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define INF 2000000000
inline int read() {
int x = 0, flag = 1; char ch = getchar(); while (!isdigit(ch)) { if (!(ch ^ '-')) flag = -1; ch = getchar(); }
while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * flag;
}
int n, m, sum;
int S, T;
struct edge { int v, c, next; }e[220001];
int head[N], tot = 1;
int q[N], dep[N];
inline void insert(int u, int v, int c) { e[++tot].v = v, e[tot].c = c, e[tot].next = head[u]; head[u] = tot; }
inline void add(int u, int v, int c) { insert(u, v, c), insert(v, u, 0); }
inline bool bfs() {
memset(dep, 0, sizeof dep); dep[S] = 1;
int l = 1, r = 1; q[1] = S;
while (l <= r) {
int u = q[l++];
for (int i = head[u], v; i; i = e[i].next) if (e[i].c && !dep[v = e[i].v]) {
dep[v] = dep[u] + 1, q[++r] = v;
if (!(v ^ T)) return 1;
}
}
return 0;
}
int dfs(int u, int dist) {
if (!(u ^ T) || !dist) return dist;
int ret = 0;
for (int i = head[u], v, c; i; i = e[i].next) if ((c = e[i].c) && !(dep[v = e[i].v] ^ (dep[u] + 1))) {
int d = dfs(v, min(dist, c));
dist -= d, ret += d, e[i].c -= d, e[i ^ 1].c += d;
if (!dist) break;
}
return ret;
}
int dinic() { int ret = 0; while (bfs()) ret += dfs(S, INF); return ret; }
int main() {
n = read(), m = read(); T = 2 * n + 1;
rep(i, 1, n) { int f = read(); add(S, i, f), add(i + n, T, f); sum += f; }
rep(i, 1, m) { int u = read(), v = read(), c = read(); add(u, v + n, c); }
printf("%d", sum - dinic());
return 0;
}