Snow
题目背景
SOURCE：NOIP2015-SHY4
题目描述
有一天，TT 要去 ABC 家。ABC 的大门外有 n 个站台，用 1 到 n 的正整数编号，TT 需要对每个站台访问恰好一定次数以后才能到 ABC 家。站台之间有 m 个单向的传送门，通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门，TT 就需要乘坐公共汽车，并花费 1 单位的钱。值得庆幸的是，任意两个站台之间都有公共汽车直达。
现在给定每个站台必须访问的次数，对于站台 i ，TT 必须恰好访问 Fi 次（不能超过）。
我们用 u，v，w 三个参数描述一个传送门，表示从站台 u 到站台 v 有一个最多可以使用 w 次的传送门（不一定要使用 w 次）。对于任意一对传送门 (u1,v1)" role="presentation" style="position: relative;">(u1,v1)(u1,v1) 和 (u2,v2)" role="presentation" style="position: relative;">(u2,v2)(u2,v2)，如果有u1<u2" role="presentation" style="position: relative;">u1<u2u1<u2，则有v1≤v2" role="presentation" style="position: relative;">v1≤v2v1≤v2；如果有v1<v2" role="presentation" style="position: relative;">v1<v2v1<v2，则有 u1≤u2" role="presentation" style="position: relative;">u1≤u2u1≤u2；且u1=u2" role="presentation" style="position: relative;">u1=u2u1=u2 和 v1=v2" role="presentation" style="position: relative;">v1=v2v1=v2 不同时成立。
TT 可以从任意的站台开始，从任意的站台结束。出发去开始的站台需要花费 1 单位的钱。现在请帮助 TT 求出打开大门最少需要花费多少单位的钱。
输入格式
第一行包含两个正整数 n，m，意义见题目描述。
第二行包含 n 个正整数，第 i 个数表示 Fi。
接下来有 m 行，每行有三个正整数 u，v，w，表示从 u 到 v 有一个可以使用 w 次的传送门。
输出格式
输出仅一行包含一个整数表示答案。
样例数据 1
输入
4 3
5 5 5 5
1 2 1
3 2 1
3 4 1
输出
17
备注
【数据范围】
有 20% 的数据满足 n≤10,m≤50；
有 50% 的数据满足 n≤1000，m≤10000；
100% 的数据满足 1≤n≤10000，1≤m≤100000；
对于所有的 u，v，满足 1≤u,v≤n；u≠v；对于所有的 w,Fi，满足 1≤w,Fi≤50000。
以上的每类数据中都存在 50% 的数据满足对于所有的 w,Fi，有 w=Fi=1。
考试的时候并没有发现题目的限制条件可以推出这是一个DAG，DAG的话不就是一个差不多裸的最大流了吗？求出最多可以利用多少传送门，用总的f[i]的和减去可利用的传送门的个数就是答案。
代码：
#include<bits/stdc++.h>
#define N 50005
#define M 1000005
#define inf 1000000000
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m,f[N],first[N],cnt=-1,d[N],s,t;
struct Node{int v,next,c;}e[M<<1];
inline void add(int u,int v,int c){e[++cnt].v=v,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}
inline bool bfs(){
queue<int>q;
q.push(s);
memset(d,-1,sizeof(d));
d[s]=0;
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=first[x];i!=-1;i=e[i].next){
int v=e[i].v;
if(e[i].c<=0||d[v]!=-1)continue;
d[v]=d[x]+1;
if(v==t)return true;
q.push(v);
}
}
return false;
}
inline int dfs(int x,int f){
if(!f||x==t)return f;
int flow=f;
for(int i=first[x];i!=-1;i=e[i].next){
int v=e[i].v;
if(flow&&e[i].c>0&&d[v]==d[x]+1){
int tmp=dfs(v,min(flow,e[i].c));
if(tmp==0)d[v]=-1;
flow-=tmp;
e[i].c-=tmp;
e[i^1].c+=tmp;
}
}
return f-flow;
}
inline int maxflow(){
int ret=0;
while(bfs())ret+=dfs(s,inf);
return ret;
}
int main(){
memset(first,-1,sizeof(first));
int ans=0;
n=read(),m=read();
for(int i=1;i<=n;++i)ans+=(f[i]=read());
s=0,t=n*2+1;
for(int i=1;i<=n;++i)add(s,i,f[i]),add(i,s,0),add(i+n,t,f[i]),add(t,i+n,0);
for(int i=1;i<=m;++i){int u=read(),v=read(),w=read();add(u,v+n,w),add(v+n,u,0);}
cout<<ans-maxflow();
return 0;
}