[文章目录]
Description
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。n<=1000 m<=10000 ai,ci<=2^31-1
设第i种志愿者雇佣个数为x[i]，那么题目限制可以转化为：
x[j] (lj<=i<=rj)>=a[i]
加一个变量：y[i]，表示第i天多雇的志愿者个数。那么则有：
x[j] (lj<=i<=rj)+y[i]=a[i]
增加第0，n+1天的a[i]=0，差分方程：
x[j] (i==lj)- x[j] (i==rj+1)+y[i]-y[i-1]+a[i]-a[i-1]=0
将每个点看做方程，加看做流进，减相当于流出，每个点收支平衡。对于方程中的x，我们由r+1向l连边，费用为c，i+1向i连边，流量为inf，判断a[i]-a[i-1]的正负，如果为正由s向i连边，流量为a[i]-a[i-1]，反之则由i向t连边。
模型的最小费用最大流即为答案。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
int n,m,s,t,b[1100];
int head[1100],to[40000],nxt[40000],w[40000],cnt=1;
ll f[40000];
inline void add(int x,int y,ll z,int ww)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z; w[cnt]=ww;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0; w[cnt]=-ww;
}
queue<int>q;
ll dis[1100];
int path[1100];
bool vis[1100];
bool spfa()
{
memset(dis,0x3f,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0; q.push(s); vis[s]=1; int x;
while(!q.empty())
{
x=q.front(); q.pop(); vis[x]=0;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]>dis[x]+w[i])
{
dis[to[i]]=dis[x]+w[i];
path[to[i]]=i^1;
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
return dis[t]<inf;
}
ll mincost()
{
ll re=0;
while(spfa())
{
ll flow=inf;
for(int i=t;i!=s;i=to[path[i]]) flow=min(flow,f[path[i]^1]);
for(int i=t;i!=s;i=to[path[i]])
{
f[path[i]]+=flow; f[path[i]^1]-=flow;
re+=flow*w[path[i]^1];
}
}
return re;
}
int main()
{
scanf("%d%d",&n,&m); s=n+2; t=s+1;
for(int i=1;i<=n;++i) scanf("%d",b+i);
for(int i=n+1;i;--i) b[i]=b[i-1]-b[i];
for(int i=0;i<=n+1;++i)
{
if(b[i]>0) add(s,i,b[i],0);
else add(i,t,-b[i],0);
}
int l,r,w;
while(m--)
{
scanf("%d%d%d",&l,&r,&w);
add(r+1,l,inf,w);
}
for(int i=0;i<=n;++i) add(i,i+1,inf,0);
printf("%lld",mincost());
return 0;
}