Solution

两种模型：https://www.cnblogs.com/iiyiyi/p/5616080.html
这一种是直接分析不等式然后转化成网络流，是可以看懂的那一种。

然后是 luogu 题解第一篇的那个模型。
考虑一开始有 $INF$ 个免费志愿者。
然后到某条边开始只限制 $INF-a_i$ 个免费志愿者通过。你最终需要让 $INF$ 个全部免费志愿者通过，所以碰到这种边我们必须让志愿者付费通过。
对于每条边我们发现，如果它的流量是 $INF-a_i$，则一定至少有 $a_i$ 个免费志愿者通过付费道路跨过它。
再经过思考可以得知，这种模型与该问题是完全等价的（大概）。

Code

// Code by ajcxsu
// Problem: zyzzm

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10, M=2e4+10; int s, t;
int h[N], to[M], nexp[M], W[M], V[M], p=2;
inline void ins(int a, int b, int w, int v) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, V[p]=v, p++; }
inline void sins(int a, int b, int c, int d) { ins(a, b, c, d), ins(b, a, 0, -d); }
#define INF (0x3f3f3f3f)
#define CLR(x, y) memset(x, y, sizeof(x))

int cost, flow;
int dist[N], pre[N], preu[N];
bool S[N];
bool spfa() {
    queue<int> qu;
    qu.push(s);
    CLR(dist, 0x3f), CLR(pre, -1); dist[s]=0;
    int na;
    while(!qu.empty()) {
        na=qu.front(), qu.pop(), S[na]=0;
        for(int u=h[na];u;u=nexp[u])
            if(W[u] && dist[to[u]]>dist[na]+V[u]) {
                dist[to[u]]=dist[na]+V[u], pre[to[u]]=na, preu[to[u]]=u;
                if(!S[to[u]]) S[to[u]]=1, qu.push(to[u]);
            }
    }
    if(pre[t]==-1) return 0;
    int nfl=0x3f3f3f3f; na=t;
    while(pre[na]!=-1) {
        nfl=min(nfl, W[preu[na]]);
        na=pre[na];
    }
    na=t;
    cost+=nfl*dist[t];
    while(pre[na]!=-1) {
        W[preu[na]]-=nfl, W[preu[na]^1]+=nfl;
        na=pre[na];
    }
    flow+=nfl;
    return nfl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin>>n>>m;
    s=0, t=n+1;
    int u, v, w;
    int na;
    sins(0, 1, INF, 0);
    for(int i=1;i<=n;i++) cin>>na, sins(i, i+1, INF-na, 0);
    for(int i=0;i<m;i++) cin>>u>>v>>w, sins(u, v+1, INF, w);
    while(spfa());
    cout<<cost<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3980.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆