2018 BUPT Summer Training 网络流

A - Drainage Ditches POJ - 1273

板子题,没什么好说的

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
    int to,cap,rev;
};
vector<edge>G[210];
int level[205],iter[205];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))
            flow+=f;
    }
}
int main()
{
    int n,m,i,j,k;
    while(cin>>n>>m){
        for(i=1;i<=200;i++)G[i].clear();
        for(i=1;i<=n;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);
        }
        cout<<maxflow(1,m)<<endl;
    }

    return 0;
}

C - Reactor Cooling ZOJ - 2314

无源汇可行流模板题

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
struct edge{
    int to,cap,rev,id;
};
vector<edge>G[210];
int level[205],iter[205],cha[205],lower[200005],cur[205];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))
            flow+=f;
    }
}
struct ans{
    int id,cap;
    bool operator<(const ans v)const{
        return id<v.id;
    }
};
int main() {
    int n, m, i, j, k,t;
    cin>>t;
    while(t--) {
        cin>>n>>m;memset(cur,0,sizeof(cur));
        for(i=0;i<205;i++)G[i].clear();
        for (i = 1; i <= m; i++) {
            int a, b, d;
            scanf("%d%d%d%d", &a, &b, &lower[i], &d);
            cur[b] += lower[i];
            cur[a] -= lower[i];
            addedge(a, b, d - lower[i]);
            G[a].back().id = i;//记录边的id
        }
        int sum = 0;
        for (i = 1; i <= n; i++) {
            if (cur[i] > 0) {
                addedge(0, i, cur[i]);
                sum += cur[i];
            } else if (cur[i] < 0) {
                addedge(i, 201, -cur[i]);
            }
        }
        int flow = maxflow(0, 201);
        if (flow != sum) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        vector<ans> as;//存答案
        for (i = 1; i <= n; i++) {
            for (j = 0; j < G[i].size(); j++) {
                edge e = G[i][j];
                if (!e.id)continue;//反向边或者连向附加汇点的边无视
                as.push_back(ans{e.id, G[e.to][e.rev].cap + lower[e.id]});//这条边的反向边的容量+这条边的下界
            }
        }
        sort(as.begin(), as.end());
        for (i = 0; i < as.size(); i++) {
            printf("%d\n", as[i].cap);
        }
    }

    return 0;
}

D - Number HYSBZ - 3275

注意题目条件是同时满足两个条件的数才不能一起选。对于每个点a,我们拆成$a_x$和$a_y$,源点连接$a_x$,容量为数值,$a_y$连接汇点,容量为数值。如果两个数a,b不能同时选,那么我们就将$a_x$连接$b_y$,$b_x$ 连接$a_y$,容量为INF。那么答案就是所有数的和-maxflow/2

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
struct edge{
    int to,cap,rev,id;
};
vector<edge>G[210];
int level[205],iter[205],cha[205],lower[200005],cur[205];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))
            flow+=f;
    }
}
struct ans{
    int id,cap;
    bool operator<(const ans v)const{
        return id<v.id;
    }
};
int main() {
    int n, m, i, j, k,t;
    cin>>t;
    while(t--) {
        cin>>n>>m;memset(cur,0,sizeof(cur));
        for(i=0;i<205;i++)G[i].clear();
        for (i = 1; i <= m; i++) {
            int a, b, d;
            scanf("%d%d%d%d", &a, &b, &lower[i], &d);
            cur[b] += lower[i];
            cur[a] -= lower[i];
            addedge(a, b, d - lower[i]);
            G[a].back().id = i;//记录边的id
        }
        int sum = 0;
        for (i = 1; i <= n; i++) {
            if (cur[i] > 0) {
                addedge(0, i, cur[i]);
                sum += cur[i];
            } else if (cur[i] < 0) {
                addedge(i, 201, -cur[i]);
            }
        }
        int flow = maxflow(0, 201);
        if (flow != sum) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        vector<ans> as;//存答案
        for (i = 1; i <= n; i++) {
            for (j = 0; j < G[i].size(); j++) {
                edge e = G[i][j];
                if (!e.id)continue;//反向边或者连向附加汇点的边无视
                as.push_back(ans{e.id, G[e.to][e.rev].cap + lower[e.id]});//这条边的反向边的容量+这条边的下界
            }
        }
        sort(as.begin(), as.end());
        for (i = 0; i < as.size(); i++) {
            printf("%d\n", as[i].cap);
        }
    }

    return 0;
}

E - 软件开发 HYSBZ - 1221

非常类似餐巾计划问题。唯一的不同就是洗的时间,第i天的毛巾在i+1天才开始洗,所以在第i+k+1天才洗好,其他就没什么区别了。 关于构图: 这是一道最小费用(费用指单价)最大流的题目。 首先,我们拆点,将一天拆成晚上和早上,每天晚上会受到脏餐巾(来源:当天早上用完的餐巾,在这道题中可理解为从原点获得),每天早上又有干净的餐巾(来源:购买、快洗店、慢洗店)。(本题中对应两种清洗方式,其实就是换了个名字而已) 1.从原点向每一天晚上连一条流量为当天所用餐巾x,费用为0的边,表示每天晚上从起点获得x条脏餐巾。 2.从每一天早上向汇点连一条流量为当天所用餐巾x,费用为0的边,每天白天,表示向汇点提供x条干净的餐巾,流满时表示第i天的餐巾够用 。 3.从每一天晚上向第二天晚上连一条流量为INF,费用为0的边,表示每天晚上可以将脏餐巾留到第二天晚上(注意不是早上,因为脏餐巾在早上不可以使用)。 4.从每一天晚上向这一天+快洗所用天数t1的那一天早上连一条流量为INF,费用为快洗所用钱数的边,表示每天晚上可以送去快洗部,在地i+t1天早上收到餐巾 。 5.同理,从每一天晚上向这一天+慢洗所用天数t2的那一天早上连一条流量为INF,费用为慢洗所用钱数的边,表示每天晚上可以送去慢洗部,在地i+t2天早上收到餐巾 。 6.从起点向每一天早上连一条流量为INF,费用为购买餐巾所用钱数的边,表示每天早上可以购买餐巾 。 注意,以上6点需要建反向边!3~6点需要做判断(即连向的边必须<=n)

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge{
    int to,cap,cost,rev;//终点,容量,费用,反向边
};
vector<edge>G[5010];
int dis[5010],prevv[5010],preve[5010],n,m,s,t,flow=0,cost=0;//最短路中前驱节点和对应的边
bool inque[5010];
const int INF=1<<30;
void add(int from,int to,int cap,int cost)
{
    G[from].push_back(edge{to,cap,cost,(int)G[to].size()});
    G[to].push_back(edge{from,0,-cost,(int)G[from].size()-1});//注意反向边的加法!!-cost和cap=0!!
}
bool spfa(int s,int t)
{
    memset(dis,0x3f, sizeof(dis));memset(inque,0,sizeof(inque));
    queue<int>que;que.push(s);dis[s]=0;
    while(!que.empty()){
        int t=que.front();que.pop();inque[t]=false;
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap&&dis[e.to]>dis[t]+e.cost){
                dis[e.to]=dis[t]+e.cost;
                prevv[e.to]=t;preve[e.to]=i;
                if(!inque[e.to]){
                    que.push(e.to);inque[e.to]=true;
                }
            }
        }
    }
    if(dis[t]==0x3f3f3f3f)
        return false;
    int d=0x7f7f7f7f;
    for(int v=t;v!=s;v=prevv[v])
        d=min(d,G[prevv[v]][preve[v]].cap);//全最短路中的最小流量限制就是本次总的流量限制
    flow+=d;cost+=d*dis[t];
    for(int v=t;v!=s;v=prevv[v]){
        edge&e=G[prevv[v]][preve[v]];//更新路径信息
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
    }
    return true;
}
void mincostmaxflow(int s,int t)
{
    while(spfa(s,t));
}
int main()
{
    int n,a,b,f,fa,fb,i,j,k;
    cin>>n>>a>>b>>f>>fa>>fb;
    int peo[1005];
    for(i=1;i<=n;i++)scanf("%d",&peo[i]);
    for(i=1;i<=n;i++)
        add(0,i,peo[i],0);
    for(i=1;i<=n;i++)
        add(i+n,2005,peo[i],0);
    for(i=1;i<n;i++)
        add(i,i+1,INF,0);
    for(i=1;i+a+1<=n;i++)
        add(i,i+a+n+1,INF,fa);
    for(i=1;i+b+1<=n;i++)
        add(i,i+b+n+1,INF,fb);
    for(i=1;i<=n;i++)
        add(0,i+n,INF,f);
    mincostmaxflow(0,2005);
    cout<<cost<<endl;

    return 0;
}

F - 修车 HYSBZ - 1070

题目的难点在于怎么去计算总的等待时间。方法是把修车人员拆成n个点,每个人的第i个点分别表示这个人在倒数第i个对某辆车进行修理,那么等待修的车连向这个点的边就应该是 修车时间* i,因为还有i个人在等这个修车师傅。然后跑最小费用流即可。

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e3+5;
struct edge{
    int to,cap,cost,rev;//终点,容量,费用,反向边
};
vector<edge>G[maxn];
int dis[maxn],prevv[maxn],preve[maxn],n,m,s,t,flow=0,cost=0;//最短路中前驱节点和对应的边,
// 小心cost爆int,多组数据时记得清零
bool inque[maxn];
void add(int from,int to,int cap,int cost)
{
    G[from].push_back(edge{to,cap,cost,(int)G[to].size()});
    G[to].push_back(edge{from,0,-cost,(int)G[from].size()-1});//注意反向边的加法!!-cost和cap=0!!
}
bool spfa(int s,int t)
{
    memset(dis,0x3f, sizeof(dis));memset(inque,0,sizeof(inque));
    queue<int>que;que.push(s);dis[s]=0;
    while(!que.empty()){
        int t=que.front();que.pop();inque[t]=false;
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap&&dis[e.to]>dis[t]+e.cost){
                dis[e.to]=dis[t]+e.cost;
                prevv[e.to]=t;preve[e.to]=i;
                if(!inque[e.to]){
                    que.push(e.to);inque[e.to]=true;
                }
            }
        }
    }
    if(dis[t]==0x3f3f3f3f)//小心爆int的情况
        return false;
    int d=0x7f7f7f7f;
    for(int v=t;v!=s;v=prevv[v])
        d=min(d,G[prevv[v]][preve[v]].cap);//全最短路中的最小流量限制就是本次总的流量限制
    flow+=d;cost+=d*dis[t];
    for(int v=t;v!=s;v=prevv[v]){
        edge&e=G[prevv[v]][preve[v]];//更新路径信息
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
    }
    return true;
}
void mincostmaxflow(int s,int t)
{
    while(spfa(s,t));
}
int main()
{
    int m,n,i,j,k,a,b;
    cin>>m>>n;
    for(i=1;i<=n;i++)
        add(0,n*m+i,1,0);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
        cin>>a;
        for(k=1;k<=n;k++){
            add(n*m+i,(j-1)*n+k,1,a*k);
        }
    }
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            add((i-1)*n+j,900,1,0);
    mincostmaxflow(0,900);
    printf("%.2f\n",(double)cost/n);

    return 0;
}

G - Firing POJ - 2987

最大权闭合图的模板题

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=5e3+5;
struct edge{
    int to,cap,rev;
};
vector<edge>G[maxn];
int level[maxn],iter[maxn];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
long long  maxflow(int s,int t){
    long long flow=0;//小心爆int
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        long long f;
        while(f=dfs(s,t,0x7f7f7f7f))//注意如果爆int这里初始最大值要更改最大值
            flow+=f;
    }
}
bool vis[maxn];int cnt=0;
void dfs(int x)
{
    vis[x]=true;cnt++;
    for(int i=0;i<G[x].size();i++){
        if(G[x][i].cap>0&&!vis[G[x][i].to])
            dfs(G[x][i].to);
    }
}
int main()
{
    int n,m,i,j,k;
    cin>>n>>m;
    long long sum=0;
    for(i=1;i<=n;i++){
        scanf("%d",&j);
        if(j>=0){
            addedge(0,i,j);sum+=j;
        }
        else{
            addedge(i,5001,-j);
        }
    }
    for(i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(a,b,1<<30);
    }
    sum-=maxflow(0,5001);
    dfs(0);
    cout<<cnt-1<<' '<<sum<<endl;

    return 0;
}

H - Being a Hero HDU - 3251

添加汇点T,原图上的单向边依次建边,容量为花费,允许选择的f个点向汇点T连边,容量为点上权值。跑一遍最小割得到花费值cost,然后用总的能获得利润(就是f个点的权值之和)减去cost 从源点S在残留网络中dfs遍历能走到的点,那么这些点就是属于S集,其他剩下的点就属于T集了, 然后判断边的两个点所属的集合,如果属于不同的集合那么这条边就是割边。 对于原图上的边如果被割到,那么这条边就是要破坏的,需要特别注意的是一定要标记每条边是不是原图中的边,否则很可能反向边会被误判为割边!!!

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1e3+5;
struct edge{
    int to,cap,rev,id;
    bool iscor;
};
vector<edge>G[maxn];
int level[maxn],iter[maxn];
void addedge(int from,int to,int cap,int id)
{
    G[from].push_back(edge{to,cap,(int)G[to].size(),id,true});
    G[to].push_back(edge{from,0,(int)G[from].size()-1,id,false});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;//小心爆int
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))//注意如果爆int这里初始最大值要更改最大值
            flow+=f;
    }
}
bool vis[1005];
void dfs(int x)
{
    vis[x]=true;
    for(int i=0;i<G[x].size();i++){
        if(G[x][i].cap>0&&!vis[G[x][i].to]){
            dfs(G[x][i].to);
        }
    }
}
int main()
{
    int t,i,j,k,n,m,f;
    cin>>t;int case1=0;
    while(t--){
        case1++;
        cin>>n>>m>>f;
        for(i=1;i<=1001;i++)G[i].clear();
        //int ava[1005]={0};
        for(i=1;i<=m;i++){
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w,i);//连边
        }
        long long sum=0;
        while(f--){
            int u,w;scanf("%d%d",&u,&w);sum+=w;//ava[u]=1;
            addedge(u,1001,w,0);//1001为汇点
        }
        printf("Case %d: ",case1);
        cout<<sum-maxflow(1,1001)<<endl;
        memset(vis,0,sizeof(vis));
        dfs(1);
        vector<int>road;//破坏的边
        for(i=1;i<=n;i++){
            for(j=0;j<G[i].size();j++){
                edge e=G[i][j];
                if(vis[i]&&!vis[e.to]&&e.id&&e.iscor){
                    road.push_back(e.id);
                }
            }
        }
        cout<<road.size();
        //sort(road.begin(),road.end());
        for(i=0;i<road.size();i++)
            cout<<' '<<road[i];
        cout<<endl;
    }

    return 0;
}

I - 志愿者招募 HYSBZ - 1061

源点连第一天,最后一天(n+1)连汇点,容量为INF费用为0 这样跑网络流是沿时间流的(就是依次解决每一天的问题) 然后每一天向后一天连一条容量为INF-a[i],费用为0的边(这其实是本题精髓) 为什么容量为INF-a[i]?这就相当于少了a[i],得用带权边也就是招来的志愿者补全INF 这就是志愿者连续干时沿这条边跑,因为连续干不花钱,所以优先选这种边 然后将每一类志愿者s[i]与t[i]+1连一条容量为INF花费为c[i]的边,当连续干的人不够时,就得充钱使劲往里塞人,补全INF。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int INF = (1 << 31) - 1;
struct edge {
    int to, cap, cost, rev;
};
vector<edge>G[2010];
int dis[2010], prevv[2010], preve[2010], n, m, flow = 0, cost = 0;
bool inque[2010];
void add(int from, int to, int cap, int cost)
{
    edge e;
    e.to = to; e.cap = cap; e.cost = cost; e.rev = G[to].size();
    G[from].push_back(e);
    e.to = from; e.cap = 0; e.cost = -cost; e.rev = G[from].size() - 1;//-cost!
    G[to].push_back(e);
}
bool Spfa(int s, int t)
{
    fill(dis, dis + 2000, 1 << 30); memset(inque, 0, sizeof(inque));
    queue<int>que;
    dis[s] = 0; inque[s] = true; que.push(s);
    while (!que.empty()) {
        int t = que.front(); que.pop(); inque[t] = false;
        for (int i = 0; i < G[t].size(); i++) {
            edge e = G[t][i];
            if (e.cap&&dis[e.to] > dis[t] + e.cost) {
                dis[e.to] = dis[t] + e.cost;
                prevv[e.to] = t;
                preve[e.to] = i;//一个边一个点不要混淆!
                if (!inque[e.to]) {
                    que.push(e.to);
                    inque[e.to] = true;
                }
            }
        }
    }
    if (dis[t] == 1 << 30)//如果已经无法增广,返回
        return false;
    int d = 1 << 30;
    for (int v = t; v != s; v = prevv[v])
        d = min(d, G[prevv[v]][preve[v]].cap);//此次可增广容量是全路径中容量最小的那个
    flow += d;
    cost += d * dis[t];//dis是路径中单位费用和
    for (int v = t; v != s; v = prevv[v]) {//更改容量
        edge &e = G[prevv[v]][preve[v]];
        e.cap -= d;
        G[v][e.rev].cap += d;//v或者e.to都可以
    }
    return true;
}
void mincostmaxflow(int s, int t)
{
    while (Spfa(s, t)&&flow<INF);
}
int main()
{
    int i, j;
    cin >> n >> m;
    add(0, 1, INF, 0); add(n + 1, 1500, INF, 0);
    for (i = 1; i <= n; i++) {
        scanf("%d", &j);
        add(i, i + 1, INF - j, 0);
    }
    for (i = 1; i <= m; i++) {
        int s, t, c;
        scanf("%d %d %d", &s, &t, &c);
        add(s, t + 1, INF, c);
    }
    mincostmaxflow(0, 1500);
    cout << cost << endl;

    return 0;
}