【NOI2008】志愿者招募

和【2017山东day7】养猫做法类似。

都是神仙题。

首先我设\(c_{i,j}=[l[j]\leq i\leq r[j]]\) ，于是就可以列出下面的不等式：
\[ \displaystyle \begin{align} \sum_{i=1}^mc_{1,i}*d_i&\geq a_1\\ &...\\ \sum_{i=1}^mc_{n,i}*d_i&\geq a_n\\ 0&=0 \end{align} \]
我们加一个辅助变量\(y_i\)，使不等式变成等式，并且在最后加上\(0=0\)：
\[ \displaystyle \begin{align} \sum_{i=1}^mc_{1,i}*d_i&=y_1+a_1\\ &...\\ \sum_{i=1}^mc_{n,i}*d_i&=y_n+a_n\\ 0&=0 \end{align} \]
差分后：
\[ \begin{align} \displaystyle \sum_{i=1}^mc_{1,i}*d_i&=y_1+a_1\\ \sum_{i=1}^mc_{2,i}*d_i+y_1+a_1&=\sum_{i=1}^mc_{1,i}*d_i+y_2+a_2\\ &...\\ \sum_{i=1}^mc_{n,i}*d_i+y_{n-1}+a_{n-1} &=\sum_{i=1}^mc_{n-1,i}*d_i+y_n+a_n\\ y_n+a_n&=\sum_{i=1}^mc_{n,i}*d_i \end{align} \]
然后每个变量就会在等式左边和右边各出现一次。对于一个变量\(x\)，我们从它出现于右边的等式连一条边到它出现于左边的等式。对于常量，它出现在左边就从\(S\)连一条边到该等式，否则该等式连一条边到\(T\)。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 2005
#define M 20005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m;
int S,T;
int l[M],r[M],c[M];
int a[N];
struct road {
    int to,next;
    int flow;
    ll cost;
}s[(N+M)*5];
int h[N],cnt=1;
void add(int i,int j,int f,ll c) {
    s[++cnt]=(road) {j,h[i],f,c};h[i]=cnt;
    s[++cnt]=(road) {i,h[j],0,-c};h[j]=cnt;
} 

ll ans=0;
ll tag[N];
ll lim[N];
ll dis[N];
int fr[N],e[N];
bool in[N];
queue<int>q;
int tot;
int maxflow;

bool ins[N];
int dfs(int v,int maxf) {
    if(v==T) return maxf;
    ins[v]=1;
    int ret=0;
    for(int i=h[v];i;i=s[i].next) {
        int to=s[i].to;
        if(!ins[to]&&s[i].flow&&dis[to]==dis[v]+s[i].cost) {
            int dlt=dfs(to,min(maxf,s[i].flow));
            ret+=dlt;
            s[i].flow-=dlt;
            s[i^1].flow+=dlt;
            maxf-=dlt;
            if(!maxf) return ins[v]=0,ret;
        }
    }
    ins[v]=0;
    return ret;
}

ll dinic() {
    ll ans=0;
    while(1) {
        int tem=dfs(S,1e9);
        if(!tem) break;
        ans+=tem;
    }
    return ans;
}

bool spfa() {
    memset(dis,0x3f,sizeof(dis));
    dis[S]=0;
    q.push(S);
    while(!q.empty()) {
        int v=q.front();
        q.pop();
        in[v]=0;
        for(int i=h[v];i;i=s[i].next) {
            int to=s[i].to;
            if(s[i].flow&&dis[to]>dis[v]+s[i].cost) {
                dis[to]=dis[v]+s[i].cost;
                fr[to]=v;
                e[to]=i;
                if(!in[to]) in[to]=1,q.push(to);
            }
        }
    }
    if(dis[T]>1e9) return 0;
    ans+=dinic()*dis[T];
    return 1;
}

int main() {
    n=Get(),m=Get();
    for(int i=1;i<=n;i++) a[i]=Get();
    for(int i=1;i<=m;i++) l[i]=Get(),r[i]=Get(),c[i]=Get();
    T=n+2;
    for(int i=1;i<=n;i++) {
        add(i,T,a[i],0);
        add(S,i+1,a[i],0);
        add(i,i+1,1e9,0);
    }
    for(int i=1;i<=m;i++) {
        add(r[i]+1,l[i],1e9,c[i]);
    }
    while(spfa());
    cout<<ans;
    return 0;
}