1061: [Noi2008]志愿者招募
Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 5291 Solved: 3173
[Submit][Status][Discuss]
Description
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难
题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要
Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用
是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这
并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
Input
第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负
整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了
方便起见，我们可以认为每类志愿者的数量都是无限多的。
Output
仅包含一个整数，表示你所设计的最优方案的总费用。
Sample Input
3 3
2 3 4
1 2 2
2 3 5
3 3 2
2 3 4
1 2 2
2 3 5
3 3 2
Sample Output
14
HINT
1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1。
题解
这题dalao们要不就是用线性规划来把不定方程转化为一般方程建边跑费用流
但是有dalao提出了这样一种建边方法（我们用二元组（cap，val）表示边的流量和花费）：
- 对于每一天向后一天连边(inf−ai,0)
- 对于每一种志愿者选择，从L到R+1建边（inf，cost[i]）
- 从超级源向第一天连边(inf,0)
- 从最后一天+1向超级汇连边(inf,0)
但是为什么这样是对的呢？
原谅本蒟蒻看了许多dalao们的解释都看不懂。。。
于是我就自己YY了一下：
- 假设有一种免费志愿者，他的工作区间为（1，n）
- 我们每天都需要inf个志愿者，其中有至少a[i]个非免费志愿者，也就是最多有inf-a[i]个免费志愿者
- 所以我们对于每一天向它的下一天连边（inf-a[i]，0）意味着这一天工作完下一天继续工作的免费志愿者最多为inf-a[i]个（因为中间不能临时增加免费志愿者）
- 然后对于每个非免费志愿者i的工作区间（l,r），我们从l向r+1连一条边（inf,c[i]）表示我们这几天可以花费每人c[i]的代价让免费志愿者直接去往第r+1天，而剩下的部分由非免费志愿者补齐
- 建立超级源点向第一天连（inf，0）表示第一天可以有inf个免费志愿者
- 从第n+1天向超级汇点连（inf，0）表示最后每天都要有inf个志愿者
- 这样就可以把有下限无上限的问题转化成有上限无下限的问题
跑费用流
代码
//by 减维
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<bitset>
#include<set>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<ctime>
#include<algorithm>
#define ll long long
#define db double
#define inf 2147483647//1<<29
#define maxn 20005
#define eps 1e-8
using namespace std; inline int read()
{
int ret=;bool fla=;char ch=getchar();
while((ch<''||ch>'')&&ch!='-')ch=getchar();
if(ch=='-'){fla=;ch=getchar();}
while(ch>=''&&ch<=''){ret=ret*+ch-'';ch=getchar();}
return fla?-ret:ret;
} struct edge{
int to,ne,cap,val;
}e[maxn<<]; int n,m,s,t,ecnt=,a[maxn],head[maxn],dis[maxn];
bool pd[maxn],vis[maxn]; void add(int x,int y,int z,int k)
{
ecnt++;e[ecnt]=(edge){y,head[x],z,k};head[x]=ecnt;
ecnt++;e[ecnt]=(edge){x,head[y],,-k};head[y]=ecnt;
} bool bfs()
{
deque<int>q;q.push_back(t);
for(int i=s;i<=t;++i)dis[i]=inf;dis[t]=;
memset(pd,,sizeof pd);pd[t]=;
while(!q.empty())
{
int d=q.front();q.pop_front();
pd[d]=;
for(int i=head[d];i;i=e[i].ne)
{
int dd=e[i].to;
if(e[i^].cap&&dis[dd]>dis[d]-e[i].val)
{
dis[dd]=dis[d]-e[i].val;
if(!pd[dd]){
pd[dd]=;
if(q.empty()||dis[dd]>dis[q.front()]) q.push_back(dd);
else q.push_front(dd);
}
}
}
}
return dis[s]<inf;
} int dfs(int x,int cap)
{
vis[x]=;
if(x==t||!cap)return cap;
int tmp,ret=;
for(int i=head[x];i;i=e[i].ne)
{
int dd=e[i].to;
if(!vis[dd]&&e[i].cap&&dis[dd]==dis[x]-e[i].val)
{
tmp=dfs(dd,min(e[i].cap,cap));
cap-=tmp;ret+=tmp;
e[i].cap-=tmp;e[i^].cap+=tmp;
}
}
return ret;
} int zkw()
{
int ret=;
while(bfs())
{
vis[t]=;
while(vis[t]){
memset(vis,,sizeof vis);
ret+=dfs(s,inf)*dis[s];
}
}
return ret;
} int main()
{
n=read();m=read();
s=,t=n+;
for(int i=;i<=n;++i) a[i]=read(),add(i,i+,inf-a[i],);
for(int i=,x,l,r;i<=m;++i) l=read(),r=read(),x=read(),add(l,r+,inf,x);
add(s,,inf,);add(n+,t,inf,);
printf("%d",zkw());
return ;
}