分析

这题可谓是借差补全的典例了

一拿到题，想法肯定是源点向志愿者连费用的边，志愿者向时间段连边，时间段向t连需求的边

但是我们发现，这样的话需要把一个流量当多个流量用，不符合网络流的操作

那么我们考虑时间轴建图

我们从s[i]到t[i]+1连流量无限，费用为c[i]的边

从i到i+1连流量为无限-a[i]的边，费用为0

然后S=0到i连流量无限的边，n+1到T=n+2连流量无限的边

我们发现整个网络如果合法，最大流为Inf

但是时间轴上的限制会缩减最大流，这时候我们通过用额外的权值边补全最大流

我当时看到这个做法的时候忍不住拍案叫绝，事实证明，做题不能按照惯性思维，有时候需要颠倒常识

刚开始还以为是上下界呢= =

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const ll Inf=1ll<<62;const int N=1e3+10;const int M=1e4+10;struct Pipe {    int v,c,w,nx;}g[2*(N+M)];int cnt=1,list[N],f[N];ll dis[N],ans;bool vis[N];int n,m,s,t;void Add(int u,int v,int c,int w) {    g[++cnt]=(Pipe){v,c,w,list[u]};list[u]=cnt;    g[++cnt]=(Pipe){u,0,-w,list[v]};list[v]=cnt;}bool SPFA() {    queue
          
            q;    while (!q.empty()) q.pop();    for (int i=s;i<=t;i++) dis[i]=Inf;    q.push(s);dis[s]=0;vis[s]=1;    while (!q.empty()) {        int u=q.front();q.pop();        for (int i=list[u];i;i=g[i].nx)            if (g[i].c&&dis[g[i].v]>dis[u]+g[i].w) {                dis[g[i].v]=dis[u]+g[i].w;f[g[i].v]=i;                if (!vis[g[i].v]) q.push(g[i].v);                vis[g[i].v]=1;            }        vis[u]=0;    }    return dis[t]!=Inf;}void MCF() {    int x=t,mf=2147483647;    while (f[x]) {        mf=min(mf,g[f[x]].c);        x=g[f[x]^1].v;    }    x=t;    while (f[x]) {        ans+=g[f[x]].w*mf;        g[f[x]].c-=mf;g[f[x]^1].c+=mf;        x=g[f[x]^1].v;    }}void Dinic() {    while (SPFA()) MCF();}int main() {    scanf("%d%d",&n,&m);    s=0;t=n+2;    Add(s,1,2147483647,0);Add(n+1,t,2147483647,0);    for (int i=1,a;i<=n;i++) scanf("%d",&a),Add(i,i+1,2147483647-a,0);    for (int i=1,u,v,cost;i<=m;i++) scanf("%d%d%d",&u,&v,&cost),Add(u,v+1,2147483647,cost);    Dinic();    printf("%d",ans);}