志愿者招募 [NOI2008] [鬼畜网络流]
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
【样例说明】
招募3 名第一类志愿者和4 名第三类志愿者。
【数据规模和约定】
30%的数据中,1 ≤ N, M ≤ 10,1 ≤ Ai ≤ 10;
100%的数据中,1 ≤ N ≤ 1000,1 ≤ M ≤ 10000,题目中其他所涉及的数据均不超过2^31-1。
Solution
网络流的难点在于建模,此题的建模方法很鬼畜。
首先明确,这显然是一个最小费用最大流的题。
有一个源点S,汇点T,中间夹了n+1个点(对,就是n+1)
(α)首先,S->1和n+1->T分别连一条(INF,0)的边 ((x,y)表示容量x,代价y)
(β)然后对于i->i+1,连一条边为(INF-Ai,0)
(γ)在最后每一类志愿者,连一条Si->Ti+1(INF,Ci)的边
为什么要这样做?
我们一开始建的两条边(α)确保了到最后一定流量为INF (最大流特性)
然后再看剩下的边,会优先走(β),因为代价是0
但是由于减掉了Ai,意味着要保证满流必须走有代价的边(γ)
最后的答案就是(每次流量×代价和)的和了
Code
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;i++)
#define per(i,a,b) for(RG i=a;i>=b;i--)
#define inf (1<<30)
#define maxn 1005
#define maxm 1000005
using namespace std;
int n,m,cnt=,S,T;
int ned[maxn],head[maxn],dis[maxn],vis[maxn],pre[maxn];
struct E{
int u,v,fl,cost,next;
}e[maxm<<];
inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void add(int u,int v,int fl,int cost)
{
e[++cnt]=(E){u,v,fl,cost,head[u]},head[u]=cnt,swap(u,v);
e[++cnt]=(E){u,v,,-cost,head[u]},head[u]=cnt;
} int SPFA()
{
queue<int> que;
memset(dis,,sizeof(dis)),memset(pre,-,sizeof(pre)),memset(vis,,sizeof(vis));
que.push(S),dis[S]=;
RG u,v;
while(!que.empty())
{
u=que.front(),que.pop();vis[u]=;
for(RG i=head[u];i;i=e[i].next)
{
v=e[i].v;
if(e[i].fl>&&dis[v]>dis[u]+e[i].cost)
{
pre[v]=i;
dis[v]=dis[u]+e[i].cost;
if(!vis[v])
vis[v]=,que.push(v);
}
}
}
return pre[T]!=-;
} void MCMF()
{
int ans=;
while(SPFA())
{
RG now=T,fl=inf;
while(now!=S) fl=min(fl,e[pre[now]].fl),now=e[pre[now]].u;
ans+=dis[T]*fl;
now=T;
while(now!=S) e[pre[now]].fl-=fl,e[pre[now]^].fl+=fl,now=e[pre[now]].u; //bug
}
printf("%d",ans);
} int main()
{
n=read(),m=read(),S=,T=n+;
for(RG i=,tmp;i<=n;i++)
tmp=read(),add(i,i+,inf-tmp,);
for(RG i=,u,v,val;i<=m;i++)
u=read(),v=read(),val=read(),add(u,v+,inf,val);
add(S,,inf,),add(n+,T,inf,);
MCMF();
return ;
}
最新文章
- 【Java EE 学习 81】【CXF框架】【CXF整合Spring】
- RAID磁盘阵列笔记
- 尝试u3d中将代码与编辑器分离
- Web前端开发基础 第四课(颜色值)
- java之通过反射,来获得某对象的所有方法(类方法提取器)
- leetcode:Integer to Roman(整数转化为罗马数字)
- sql plus 和 pl/sql无法连接远程oracle数据库
- H264源码分析(二)
- linux 获取文件系统信息(磁盘信息)
- POJ1422 Air Raid 【DAG最小路径覆盖】
- DB2导入导出 学习笔记
- 自动化测试—monkeyrunner
- python tkinter学习——tkinter部件1
- [ExtJS5学习笔记]第十一节 Extjs5MVVM模式下系统登录实例
- 开源一个IE下获取XPath小工具,支持32/64位
- winform登录功能
- Python&#160;关于xpath查找XML元素的一点总结
- 在线制作css动画——CSS animate
- project 2013 设置工期为1个工作日,但开始时间与结束时间不是同一天
- MT【257】任意存在并存