bzoj 1061 志愿者招募(最小费用最大流)

时间:2022-09-28 20:31:19

[Noi2008]志愿者招募

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 3792  Solved: 2314
[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。

表示并不懂为何这么建图,下面是大神的详细解读。

http://www.byvoid.com/blog/noi-2008-employee/#more-916  STO.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 0x7fffffff
#define mod 10000
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N=;
const int M=;
int n,m,cnt=,ans,T=;
int head[N],q[N],dis[N],from[N];
bool inq[N];
struct data {
int from,to,next,v,c;
} e[M];
void ins(int u,int v,int w,int c) {
e[++cnt].from=u;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
e[cnt].v=w;
e[cnt].c=c;
}
void insert(int u,int v,int w,int c) {
ins(u,v,w,c);
ins(v,u,,-c);
}
bool spfa() {
int t=,w=;
for(int i=; i<=T; i++)dis[i]=inf;
q[t]=;
dis[]=;
inq[]=;
while(t!=w) {
int now=q[t];
t++;
if(t==)t=;
for(int i=head[now]; i; i=e[i].next)
if(e[i].v&&dis[now]+e[i].c<dis[e[i].to]) {
dis[e[i].to]=dis[now]+e[i].c;
from[e[i].to]=i;
if(!inq[e[i].to]) {
inq[e[i].to]=;
q[w++]=e[i].to;
if(w==)w=;
}
}
inq[now]=;
}
if(dis[T]==inf)return ;
return ;
}
void mcf() {
int x=inf;
for(int i=from[T]; i; i=from[e[i].from])
x=min(x,e[i].v);
for(int i=from[T]; i; i=from[e[i].from]) {
e[i].v-=x;
e[i^].v+=x;
ans+=e[i].c*x;
}
}
void init() {
scanf("%d%d",&n,&m);
int l=,r;
for(int i=; i<=n; i++) {
scanf("%d",&r);
int x=r-l;
if(x>)insert(,i,x,);
else insert(i,T,-x,);
insert(i+,i,inf,);
l=r;
}
insert(n+,T,l,);
for(int i=; i<=m; i++) {
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
insert(x,y+,inf,c);
}
}
int main() {
init();
while(spfa())mcf();
printf("%d",ans);
return ;
}

bzoj 1061 志愿者招募(最小费用最大流)的更多相关文章

  1. BZOJ 1061 志愿者招募(最小费用最大流)

    题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1061 题意:申奥成功后,布布经过不懈努力,终于 成为奥组委下属公司人力资源部门的主管.布 ...

  2. bzoj 1061 志愿者招募 有上下界费用流做法

    把每一天看作一个点,每一天的志愿者数目就是流量限制,从i到i+1连边,上下界就是(A[i],+inf). 对于每一类志愿者,从T[i]+1到S[i]连边,费用为招募一个志愿者的费用,流量为inf.这样 ...

  3. BZOJ 1061 志愿者招募 最小费用流&amp&semi;&amp&semi;线性规划建模

    题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1061 题目大意: 申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主 ...

  4. BZOJ 1927 星际竞速&lpar;最小费用最大流&rpar;

    题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1927 题意:一个图,n个点.对于给出的每条边 u,v,w,表示u和v中编号小的那个到编号 ...

  5. BZOJ 2424&colon; &lbrack;HAOI2010&rsqb;订货&lpar;最小费用最大流&rpar;

    最小费用最大流..乱搞即可 ------------------------------------------------------------------------------ #includ ...

  6. bzoj 1061 志愿者招募 费用流

    详见BYV的博客,写的非常全面https://www.byvoid.com/blog/noi-2008-employee /************************************** ...

  7. BZOJ&period;3265&period;志愿者招募加强版&lpar;费用流SPFA&rpar;

    题目链接 见上题. 每类志愿者可能是若干段,不满足那个...全幺模矩阵(全单位模矩阵)的条件,所以线性规划可能存在非整数解. 于是就可以用费用流水过去顺便拿个rank2 233. //20704kb ...

  8. BZOJ 1070&colon; &lbrack;SCOI2007&rsqb;修车 &lbrack;最小费用最大流&rsqb;

    1070: [SCOI2007]修车 Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 4936  Solved: 2032[Submit][Status] ...

  9. BZOJ 1061 志愿者招募

    http://www.lydsy.com/JudgeOnline/problem.php?id=1061 思路:可以用不等式的改装变成费用流. 将不等式列出,如果有负的常数,那么就从等式连向T,如果是 ...

随机推荐

  1. yxcms后台验证码不显示?怎么取消yxcms后台验证码

    嗨,大家好,我是YXCMS的小M老湿,(其实还是习惯大家叫我猪猪吧!)今天又要分享一则yxcms的使用技巧,当然也是yxcms用户在使用过程中很容易出现的小白问题,当然还是同样,yxcms的大神级别的 ...

  2. C&num;开发中Windows域认证登录2(扩展吉日嘎拉GPM系统)

    原文地址:http://www.cuiwenyuan.com/shanghai/post/Windows-AD-Logon-Intergrated-into-Jirigala-GPM-DotNet-B ...

  3. 【leetcode】Unique Paths II

    Unique Paths II Total Accepted: 22828 Total Submissions: 81414My Submissions Follow up for "Uni ...

  4. 【python cookbook】【数据结构与算法】1将序列分解为单独的变量

    如果对象是可迭代的(任何序列),则可以进行分解操作,包括元组.列表.字符串.文件.迭代器以及生成器,可通过简单的一个赋值操作分解为单独的变量. 唯一要求:变量的总数和序列相吻合,否则将出错: Pyth ...

  5. MJRefresh&lpar;上拉加载下拉刷新&rpar;

    整理自:https://github.com/CoderMJLee/MJRefresh#%E6%94%AF%E6%8C%81%E5%93%AA%E4%BA%9B%E6%8E%A7%E4%BB%B6%E ...

  6. java枚举类型构造方法为什么是private的

    枚举类型是单例模式的.你需要实例化一次,然后再整个程序之中就可以调用他的方法和成员变量了.枚举类型使用单例模式是因为他的值是固定的,不需要发生改变.更多知识见 http://blog.yemou.ne ...

  7. BZOJ 2733&colon; &lbrack;HNOI2012&rsqb;永无乡 &lbrack;splay启发式合并&rsqb;

    2733: [HNOI2012]永无乡 题意:加边,询问一个连通块中k小值 终于写了一下splay启发式合并 本题直接splay上一个节点对应图上一个点就可以了 并查集维护连通性 合并的时候,把siz ...

  8. phpstorm使用之——常用快捷键

    phpstorm使用之--常用快捷键 使用IDE的根本所在乃是为了提高工作效率. windows下phpstorm的快捷键 ctrl+shift+n查找文件 ctrl+shift+f 在一个目录里查找 ...

  9. 背水一战 Windows 10 &lpar;108&rpar; - 通知(Tile)&colon; application tile 基础&comma; secondary tile 基础

    [源码下载] 背水一战 Windows 10 (108) - 通知(Tile): application tile 基础, secondary tile 基础 作者:webabcd 介绍背水一战 Wi ...

  10. thinkphp 实现分页

    一.一个条件的查询数据 查询数据自然是先要显示出数据,然后根据条件进行查询数据 (1)显示出表的数据 这个方法我还是写在了HomeController.class控制器文件中 (1.1)写了一个方法s ...