思路
巧妙的建图
因为每个志愿者有工作的时段，所以考虑让一个志愿者的流量能够从S流到T产生贡献
所以每个i向i+1连INF-a[x]的边（类似于k可重区间集），每个si向ti连边cap=INF，cost=ci的边
相当于就是最大流要补全到INF，然后这个边的边权少了a[x]，然后为了补全到INF，并且前面还有一个能从s向t能走的边可以通过流量（相当于加一个人），然后最大流就会补上这部分流量
然后MCMF就好了
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
struct Edge{int u,v,cap,cost,flow;
};
const int MAXN = 50000;
const int INF = 0x3f3f3f3f;
vector<Edge> edges;
vector<int> G[MAXN];
void addedge(int u,int v,int cap,int cost){edges.push_back((Edge){u,v,cap,cost,0});edges.push_back((Edge){v,u,0,-cost,0});int cnt=edges.size();G[u].push_back(cnt-2);G[v].push_back(cnt-1);
}
int d[MAXN],a[MAXN],p[MAXN],s,t,vis[MAXN],n,m;
queue<int> q;
bool spfa(int &flow,int &cost){memset(d,0x3f,sizeof(d));memset(p,0,sizeof(p));q.push(s);a[s]=INF;d[s]=0;vis[s]=true;while(!q.empty()){int x=q.front();q.pop();vis[x]=false;for(int i=0;i<G[x].size();i++){Edge &e = edges[G[x][i]];if(e.cap>e.flow&&d[x]+e.cost<d[e.v]){d[e.v]=d[x]+e.cost;a[e.v]=min(a[x],e.cap-e.flow);p[e.v]=G[x][i];if(!vis[e.v]){vis[e.v]=true;q.push(e.v);}}}}if(d[t]==INF)return false;flow+=a[t];cost+=a[t]*d[t];for(int i=t;i!=s;i=edges[p[i]].u){edges[p[i]].flow+=a[t];edges[p[i]^1].flow-=a[t];}return true;
}
void mcmf(int &flow,int &cost){flow=0,cost=0;while(spfa(flow,cost));
}
int main(){scanf("%d %d",&n,&m); s=MAXN-2;t=MAXN-3;for(int i=1;i<=n;i++){int x;scanf("%d",&x);addedge(i,i+1,INF-x,0);}for(int i=1;i<=m;i++){int sx,tx,cx;scanf("%d %d %d",&sx,&tx,&cx);addedge(sx,tx+1,INF,cx);}addedge(s,1,INF,0);addedge(n+1,t,INF,0);int cost,flow;mcmf(flow,cost);printf("%d\n",cost);return 0;
}