[Noi2008]志愿者招募
Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 3792 Solved: 2314
[Submit][Status][Discuss]
Description
Input
Output
仅包含一个整数,表示你所设计的最优方案的总费用。
Sample Input
2 3 4
1 2 2
2 3 5
3 3 2
Sample Output
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 志愿者招募(最小费用最大流)的更多相关文章
-
BZOJ 1061 志愿者招募(最小费用最大流)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1061 题意:申奥成功后,布布经过不懈努力,终于 成为奥组委下属公司人力资源部门的主管.布 ...
-
bzoj 1061 志愿者招募 有上下界费用流做法
把每一天看作一个点,每一天的志愿者数目就是流量限制,从i到i+1连边,上下界就是(A[i],+inf). 对于每一类志愿者,从T[i]+1到S[i]连边,费用为招募一个志愿者的费用,流量为inf.这样 ...
-
BZOJ 1061 志愿者招募 最小费用流&;&;线性规划建模
题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1061 题目大意: 申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主 ...
-
BZOJ 1927 星际竞速(最小费用最大流)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1927 题意:一个图,n个点.对于给出的每条边 u,v,w,表示u和v中编号小的那个到编号 ...
-
BZOJ 2424: [HAOI2010]订货(最小费用最大流)
最小费用最大流..乱搞即可 ------------------------------------------------------------------------------ #includ ...
-
bzoj 1061 志愿者招募 费用流
详见BYV的博客,写的非常全面https://www.byvoid.com/blog/noi-2008-employee /************************************** ...
-
BZOJ.3265.志愿者招募加强版(费用流SPFA)
题目链接 见上题. 每类志愿者可能是若干段,不满足那个...全幺模矩阵(全单位模矩阵)的条件,所以线性规划可能存在非整数解. 于是就可以用费用流水过去顺便拿个rank2 233. //20704kb ...
-
BZOJ 1070: [SCOI2007]修车 [最小费用最大流]
1070: [SCOI2007]修车 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 4936 Solved: 2032[Submit][Status] ...
-
BZOJ 1061 志愿者招募
http://www.lydsy.com/JudgeOnline/problem.php?id=1061 思路:可以用不等式的改装变成费用流. 将不等式列出,如果有负的常数,那么就从等式连向T,如果是 ...
随机推荐
-
yxcms后台验证码不显示?怎么取消yxcms后台验证码
嗨,大家好,我是YXCMS的小M老湿,(其实还是习惯大家叫我猪猪吧!)今天又要分享一则yxcms的使用技巧,当然也是yxcms用户在使用过程中很容易出现的小白问题,当然还是同样,yxcms的大神级别的 ...
-
C#开发中Windows域认证登录2(扩展吉日嘎拉GPM系统)
原文地址:http://www.cuiwenyuan.com/shanghai/post/Windows-AD-Logon-Intergrated-into-Jirigala-GPM-DotNet-B ...
-
【leetcode】Unique Paths II
Unique Paths II Total Accepted: 22828 Total Submissions: 81414My Submissions Follow up for "Uni ...
-
【python cookbook】【数据结构与算法】1将序列分解为单独的变量
如果对象是可迭代的(任何序列),则可以进行分解操作,包括元组.列表.字符串.文件.迭代器以及生成器,可通过简单的一个赋值操作分解为单独的变量. 唯一要求:变量的总数和序列相吻合,否则将出错: Pyth ...
-
MJRefresh(上拉加载下拉刷新)
整理自:https://github.com/CoderMJLee/MJRefresh#%E6%94%AF%E6%8C%81%E5%93%AA%E4%BA%9B%E6%8E%A7%E4%BB%B6%E ...
-
java枚举类型构造方法为什么是private的
枚举类型是单例模式的.你需要实例化一次,然后再整个程序之中就可以调用他的方法和成员变量了.枚举类型使用单例模式是因为他的值是固定的,不需要发生改变.更多知识见 http://blog.yemou.ne ...
-
BZOJ 2733: [HNOI2012]永无乡 [splay启发式合并]
2733: [HNOI2012]永无乡 题意:加边,询问一个连通块中k小值 终于写了一下splay启发式合并 本题直接splay上一个节点对应图上一个点就可以了 并查集维护连通性 合并的时候,把siz ...
-
phpstorm使用之——常用快捷键
phpstorm使用之--常用快捷键 使用IDE的根本所在乃是为了提高工作效率. windows下phpstorm的快捷键 ctrl+shift+n查找文件 ctrl+shift+f 在一个目录里查找 ...
-
背水一战 Windows 10 (108) - 通知(Tile): application tile 基础, secondary tile 基础
[源码下载] 背水一战 Windows 10 (108) - 通知(Tile): application tile 基础, secondary tile 基础 作者:webabcd 介绍背水一战 Wi ...
-
thinkphp 实现分页
一.一个条件的查询数据 查询数据自然是先要显示出数据,然后根据条件进行查询数据 (1)显示出表的数据 这个方法我还是写在了HomeController.class控制器文件中 (1.1)写了一个方法s ...