【题解】P3980 [NOI2008]志愿者招募(费用流求线性规划)

题意

有\(m\)种志愿者以及\(n\)天，每种志愿者有固定的服务区间(天)，雇佣一个志愿者有不同的费用\(c_i\)。假设每种志愿者无限多，第\(i\)天至少要有\(a[i]\)个志愿者，问最小花费

加入辅助变量\(y_i\)把问题化为\(=a[i]\)。设\(i\)种志愿者总共\(x[i]\)个，\(b[i][j]\)表示\(i\)号志愿者是否存在于\(j\)天，那么现在我们就是一个线性规划问题了，具体的是:
\[ \min X C^T\\ \mathrm{s.t.}\\ (B,B_Y)(X,Y)^T= A^T \]

写出其中一个出来
\[ \sum_{j\in S_i} x_j-y_i= a_i \]
那么
\[ \sum_{j\in S_i} x_j- a_i-y_i=0 \]
然而我们发现，\(x_j\)的存在是一段一段的(\(B\)矩阵的行的1是连续连续的一段)，所以我们对所有的等式进行差分。可以发现所有的变量不变量都以\(+-\)的形式分别出现一次(除了最后一个方程中的变量)，这启示我们可以用网络流，因为网络流实际上就是做一个流量平衡的工作。

但是原来的最后一个方程所有变量都只出现了一次，于是我们把\(-(\text{equation }n)\)也加入方程组中这是可以用网络流解这个问题的关键。

所以现在，所有的变量都出现了两次，且分别是以+-的形式出现，于是我们可以把每个方程看做一个点，每个变量看做一条边，现在我们是要最小化\(\sum x_i c_i\)，那么直接给所有的\(x_i\)代表的边给上\(c_i\)的费用跑费用流即可。

但是网络流只能解除整数解，但是根据\(IP\)理论，这个线性规划问题存在一组整数解。

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<assert.h>
#include<queue>

using namespace std;  typedef long long ll;
inline int qr(){
    int ret=0,f=0,c=getchar();
    while(!isdigit(c))f|=c==45,c=getchar();
    while(isdigit(c)) ret=ret*10+c-48,c=getchar();
    return f?-ret:ret;
}
const int maxn=1e4+5;
const int inf=1e9;
int head[maxn],last[maxn],L[maxn],R[maxn],C[maxn],A[maxn],sum[maxn],n,m,S,T;
struct E{int to,nx,w,c;}e[maxn<<5];
void add(int fr,int to,int w,int c){
    static int cnt=1;
    e[++cnt]=(E){to,head[fr],w,c}; head[fr]=cnt;
    e[++cnt]=(E){fr,head[to],0,-c}; head[to]=cnt;
}

ll fl[maxn],d[maxn];
bool in[maxn];
ll Mincost(){
    static queue<int> q;
    ll ret=0;
    while(1){
        memset(last,0,sizeof last);
        memset(d,0x3f,sizeof d);
        memset(fl,0,sizeof fl);
        memset(in,0,sizeof in);
        while(q.size()) q.pop();
        q.push(S); d[S]=0; fl[S]=inf;
        while(q.size()){
            int now=q.front();
            q.pop(); in[now]=0;
            if(now==T) continue;
            for(int t=head[now];t;t=e[t].nx)
                if(fl[now]&&e[t].w&&d[e[t].to]>d[now]+e[t].c){
                    last[e[t].to]=t;
                    fl[e[t].to]=min(fl[now],0ll+e[t].w);
                    d[e[t].to]=d[now]+e[t].c;
                    if(!in[e[t].to]) q.push(e[t].to),in[e[t].to]=1;
                }
        }
        if(!fl[T]) break;
        ret+=d[T]*fl[T];
        for(int t=T;t!=S;t=e[last[t]^1].to)
            e[last[t]].w-=fl[T],e[last[t]^1].w+=fl[T];
    }
    return ret;
}

int main(){
    n=qr(); m=qr();
    for(int t=1;t<=n;++t) A[t]=qr();
    S=n+2,T=n+3;
    for(int t=1;t<=m;++t){
        L[t]=qr(),R[t]=qr(),C[t]=qr(),++sum[L[t]],--sum[R[t]+1];
        add(R[t]+1,L[t],inf,C[t]);
    }
    for(int t=1;t<=n;++t){
        sum[t]+=sum[t-1],assert(sum[t]>0||A[t]==0);
        if(A[t]>A[t-1]) add(t,T,A[t]-A[t-1],0);
        if(A[t]<A[t-1]) add(S,t,A[t-1]-A[t],0);
        add(t,t+1,inf,0);
    } add(S,n+1,A[n],0);
    ll ans=Mincost();
    cerr<<"ans=";
    printf("%lld\n",ans);
    return 0;
}