【费用流】BZOJ1061: [Noi2008]志愿者招募(这题超好)

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

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 ;
}
上一篇:C#使用FFMPEG推流,并且获取流保存在本地,随时取媒体进行播放!


下一篇:iOS 循环引用讲解(中)