【NOI2008】bzoj1061 志愿者招募_综合

设 $x_i$ 表示第 $i$ 类志愿者选几个， $a_i$ 表示第 $i$ 天需要多少志愿者。不难列出

\sum l j \leq i \leq r j x j = a i + b i (1 \leq i \leq n, b i > 0)

$\sum_{l_j\le i\le r_j} x_j=a_i+b_i\ \ \ (1\le i\le n,b_i\gt 0)$
注意到每个

x $x$ 都在很多等式中出现，不好处理。但是因为每种志愿者都是连续的一段，因此差分一下就可以得到

\sum l j ? 1 = i x j ? \sum r j = i x j + a i + b i ? a i + 1 ? b i + 1 = 0 (0 \leq i \leq n)

$\sum_{l_j-1=i} x_j-\sum_{r_j=i} x_j+a_i+b_i-a_{i+1}-b_{i+1}=0\ \ \ \ (0\le i\le n)$
所有变量

xi $x_i$ 和

bi $b_i$ 都只在两个等式中出现，因此可以把每个等式看成一个点，相等关系看成流量平衡，正的项看成入边，负的项看成出边，常数直接连到源汇。然后跑最小费用流就可以了。根据差分的性质可以发现所有常数边一定满流，所以不用加下界。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2020,maxm=10010,maxe=400010,s=2005,t=2006,oo=0x3f3f3f3f,p=2013;
int fir[maxn],ne[maxe],to[maxe],w[maxe],c[maxe],
mnw[maxn],pre[maxn],dis[maxn],que[maxn],inq[maxn],
A[maxn],S[maxm],T[maxm],C[maxm],
n,m,num;
void prt()
{for (int i=0;i<=t;i++)for (int j=fir[i];j;j=ne[j])if (w[j])printf("%d->%d:%d,%d\n",i,to[j],w[j],c[j]);
}
void add(int u,int v,int x,int y)
{num++;ne[num<<1]=fir[u];fir[u]=num<<1;to[num<<1]=v;w[num<<1]=x;c[num<<1]=y;ne[num<<1|1]=fir[v];fir[v]=num<<1|1;to[num<<1|1]=u;w[num<<1|1]=0;c[num<<1|1]=-y;
}
void inc(int &x)
{x=x+1==p?0:x+1;
}
int find(int &ret)
{int hd=0,tl=1,u,v;que[0]=s;for (int i=0;i<=n;i++) dis[i]=oo;dis[s]=0;dis[t]=oo;mnw[s]=oo;inq[s]=1;while (hd!=tl){u=que[hd];inc(hd);for (int i=fir[u];i;i=ne[i])if (w[i]&&dis[v=to[i]]>dis[u]+c[i]){dis[v]=dis[u]+c[i];mnw[v]=min(mnw[u],w[i]);pre[v]=i;if (!inq[v]){inq[v]=1;que[tl]=v;inc(tl);}}inq[u]=0;}if (dis[t]==oo) return 0;ret=mnw[t]*dis[t];for (int i=pre[t];i;i=pre[to[i^1]]){w[i]-=mnw[t];w[i^1]+=mnw[t];}return 1;
}
int main()
{int ans=0,x;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&A[i]);for (int i=1;i<=m;i++) scanf("%d%d%d",&S[i],&T[i],&C[i]);for (int i=0;i<=n;i++)if (A[i]>A[i+1])add(s,i,A[i]-A[i+1],0);elseadd(i,t,A[i+1]-A[i],0);for (int i=1;i<=n;i++) add(i-1,i,oo,0);for (int i=1;i<=m;i++) add(T[i],S[i]-1,oo,C[i]);//prt();while (find(x)) ans+=x;printf("%d\n",ans);
}