Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >洛谷P1251 餐巾计划问题(最小费用最大流)

洛谷P1251 餐巾计划问题(最小费用最大流)

作者头像
attack
发布于 2018-08-01 03:21:14
发布于 2018-08-01 03:21:14
36900
代码可运行
举报
运行总次数:0
代码可运行

题意

一家餐厅,第$i$天需要$r_i$块餐巾,每天获取餐巾有三种途径

1、以$p$的费用买

2、以$f$的费用送到快洗部,并在$m$天后取出

3、以$s$的费用送到慢洗部,并在$n$天后取出

问满足要求时的最小费用

Sol

一道非常不错的网络流,应该不难看出是费用流。

首先进行拆点,把每个点早上和晚上,然后进行连边

从$S$向i连边$(0, r_i)$,表示到了晚上有$r_i$块脏餐巾

从$i'$向$T$连边$(0, r_i)$,表示早上有$r_i$块新餐巾

从$S$向$i'$连边$(p, INF)$,表示每天早上可以以$p$的费用无限提供餐巾

从$i$向$i'$连边$(0, INF)$,表示每天晚上的脏餐巾可以留到第二天晚上

从$i$向$i' + m$连边$(f, INF)$,表示快洗

从$i$向$i' + n$连边$(s, INF)$,表示慢洗

这样既可以保证每天的$r_i$满足要求,又能保证最小费用。so nice

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long 
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, S, T;
int r[MAXN], p, m, f, n, s;
struct Edge {
    int u, v, w, f, nxt;
}E[MAXN];
int head[MAXN], num;
inline void add_edge(int x, int y, int w, int f) {
    E[num] = (Edge){x, y, w, f, head[x]};
    head[x] = num++;
}
inline void AddEdge(int x, int y, int w, int f) {
    add_edge(x, y, w, f);
    add_edge(y, x, -w, 0);
}
int dis[MAXN], vis[MAXN], Pre[MAXN];
bool SPFA() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q; dis[S] = 0; q.push(S);
    while(!q.empty()) {
        int p = q.front(); q.pop(); vis[p] = 0;
        for(int i = head[p]; i != -1; i = E[i].nxt) {
            int to = E[i].v;
            if(dis[to] > dis[p] + E[i].w && E[i].f) {
                dis[to] = dis[p] + E[i].w;
                Pre[to] = i;
                if(!vis[to]) vis[to] = 1, q.push(to);
            }
        }
    }
    return dis[T] <= INF;
}
LL F() {
    LL nowflow = INF;
    for(int i = T; i != S; i = E[Pre[i]].u) nowflow = min(nowflow, (LL)E[Pre[i]].f);
    for(int i = T; i != S; i = E[Pre[i]].u) E[Pre[i]].f -= nowflow, E[Pre[i] ^ 1].f += nowflow;
    return nowflow * dis[T];
}
LL MCMF() {
    LL ans = 0;
    while(SPFA()) 
        ans += F();
    return ans;
}
int main() {
    memset(head, -1, sizeof(head));
    N = read(); 
    S = 0; T = 2 * N + 1;
    for(int i = 1; i <= N; i++) r[i] = read();
    p = read(); m = read(); f = read(); n = read(); s = read();
    for(int i = 1; i <= N; i++) AddEdge(S, i, 0, r[i]);
    for(int i = 1; i <= N; i++) AddEdge(S, i + N, p, INF);
    for(int i = 1; i <= N; i++) AddEdge(i + N, T, 0, r[i]);
    for(int i = 1; i <= N; i++) {
        if(i + m <= N) AddEdge(i, i + N + m, f, INF);        
        if(i + n <= N) AddEdge(i, i + N + n, s, INF);
        if(i + 1 <= N) AddEdge(i, i + 1, 0, INF);
    }
    printf("%lld", MCMF());
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-07-26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
洛谷P4016 负载平衡问题(最小费用最大流)
题目描述 GG 公司有 nn 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。 输入输出格式 输入格式: 文件的第 11 行中有 11 个正整数 nn ,表示有 nn 个仓库。 第 22 行中有 nn 个正整数,表示 nn 个仓库的库存量。 输出格式: 输出最少搬运量。 输入输出样例 输入样例#1:  5 17 9 14 16 4 输出样例#1:  11 说明 1 \leq n \leq 1001≤n≤10
attack
2018/04/10
8070
洛谷P4014 分配问题(费用流)
题目描述 有 nn 件工作要分配给 nn 个人做。第 ii 个人做第 jj 件工作产生的效益为 c_{ij}cij​ 。试设计一个将 nn 件工作分配给 nn 个人做的分配方案,使产生的总效益最大。 输入输出格式 输入格式: 文件的第 11 行有 11 个正整数 nn ,表示有 nn 件工作要分配给 nn 个人做。 接下来的 nn 行中,每行有 nn 个整数 c_{ij}cij​ ​​,表示第 ii 个人做第 jj 件工作产生的效益为 c_{ij}cij​ 。 输出格式: 两行分别输出最小总效益和最大总效益
attack
2018/04/10
7450
洛谷P4013 数字梯形问题(费用流)
梯形的第一行有 mmm 个数字。从梯形的顶部的 mmm 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。
attack
2018/07/27
3300
洛谷P4013 数字梯形问题(费用流)
洛谷P4015 运输问题(费用流)
题目描述 WW 公司有 mm 个仓库和 nn 个零售商店。第 ii 个仓库有 a_iai​ 个单位的货物;第 jj 个零售商店需要 b_jbj​ 个单位的货物。 货物供需平衡,即\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_ji=1∑m​ai​=j=1∑n​bj​ 。 从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用为 c_{ij}cij​ ​​ 。 试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。 输入输出格式 输入格式:
attack
2018/04/10
7970
洛谷P3357 最长k可重线段集问题(费用流)
题目描述http://www.cnblogs.com/zwfymqz/p/8559566.html 给定平面 x-O-yx−O−y 上 nn 个开线段组成的集合 II ,和一个正整数 kk 。试设计一个算法,从开线段集合 II 中选取出开线段集合 S\subseteq IS⊆I ,使得在 xx 轴上的任何一点 pp ,SS 中与直线 x=px=p 相交的开线段个数不超过 kk ,且\sum\limits_{z\in S}|z|z∈S∑​∣z∣ 达到最大。这样的集合 SS 称为开线段集合 II 的最长 kk 
attack
2018/04/10
8430
洛谷P3358 最长k可重区间集问题(费用流)
题目描述 对于给定的开区间集合 I 和正整数 k,计算开区间集合 I 的最长 k可重区间集的长度。 输入输出格式 输入格式: 的第 1 行有 2 个正整数 n和 k,分别表示开区间的个数和开区
attack
2018/04/10
8770
洛谷P3358 最长k可重区间集问题(费用流)
洛谷P3356 火星探险问题(费用流)
题目描述 火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。 用一
attack
2018/04/10
6740
洛谷P4012 深海机器人问题(费用流)
题目描述 深海资源考察探险队的潜艇将到达深海的海底进行科学考察。 潜艇内有多个深海机器人。潜艇到达深海海底后,深海机器人将离开潜艇向预定目标移动。 深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。 每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。 本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可以在同一时间占据同一位置。 用一个 P\times QP×Q 网格表示深海机器人的可移动位置。西南角的坐标为 (0,0)
attack
2018/04/10
6530
洛谷P4012 深海机器人问题(费用流)
洛谷P2770 航空路线问题(费用流)
为了满足流量的限制,肯定会想到拆点,把每个点拆为两个,连流量为$1$,费用为$1$的边
attack
2018/07/27
3660
洛谷P2045 方格取数加强版(费用流)
对于拆出来的每个点,在其中连两条边,一条为费用为点权,流量为1,另一条费用为0,流量为INF
attack
2019/03/05
3650
洛谷P2774 方格取数问题(最小割)
题意 $n \times m$的矩阵,不能取相邻的元素,问最大能取多少 Sol 首先补集转化一下:最大权值 = sum - 使图不连通的最小权值 进行黑白染色 从S向黑点连权值为点权的边 从白点向T连权值为点券的边 黑点向白点连权值为INF的边 这样就转化成了最小割问题,跑Dinic即可 /* 首先补集转化一下:最大权值 = sum - 使图不连通的最小权值 进行黑白染色 从S向黑点连权值为点权的边 从白点向T连权值为点券的边 黑点向白点连权值为INF的边 跑Dinic */ #include<cstdio
attack
2018/07/27
5340
BZOJ4819: [Sdoi2017]新生舞会(01分数规划)
Description 学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。有n个男生和n个女生参加舞会 买一个男生和一个女生一起跳舞,互为舞伴。Cathy收集了这些同学之间的关系,比如两个人之前认识没计算得出  a[i][j] ,表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。Cathy还需要考虑两个人一起跳舞是否方便, 比如身高体重差别会不会太大,计算得出 b[i][j],表示第i个男生和第j个女生一起跳舞时的不协调程度。当然, 还需要考虑很多其他问题。Cathy想先用一个
attack
2018/04/10
7480
洛谷P2891 [USACO07OPEN]吃饭Dining
题目描述 Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others. Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not
attack
2018/04/11
8050
洛谷P2891 [USACO07OPEN]吃饭Dining
洛谷P4926 [1007]倍杀测量者(差分约束)
题意 题目链接 Sol 题目中的两个限制条件xian \[A_i \geqslant (K_i - T)B_i\] \[A_i(K_i + T) \geq B_i\] 我们需要让这两个至少有一个不满足 直接差分约束建边即可 这里要用到两个trick 若某个变量有固定取值的时候我们可以构造两个等式\(C_i - 0 \leqslant X, C_i - 0 \geqslant X\)。 乘法的大小判断可以取log变加法,因为\(y = log(x)\)也是个单调函数 #include<bits/stdc++.
attack
2019/03/12
4390
BZOJ4514: [Sdoi2016]数字配对(费用流)
Description 有 n 种数字,第 i 种数字是 ai、有 bi 个,权值是 ci。 若两个数字 ai、aj 满足,ai 是 aj 的倍数,且 ai/aj 是一个质数, 那么这两个数字可以配对,并获得 ci×cj 的价值。 一个数字只能参与一次配对,可以不参与配对。 在获得的价值总和不小于 0 的前提下,求最多进行多少次配对。 Input 第一行一个整数 n。 第二行 n 个整数 a1、a2、……、an。 第三行 n 个整数 b1、b2、……、bn。 第四行 n 个整数 c1、c2、……、cn。 O
attack
2018/04/03
1.1K0
洛谷P2598 [ZJOI2009]狼和羊的故事
题目描述 “狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......” Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez发现狼和羊都有属于自己领地,若狼和羊们不能呆在自己的领地,那它们就会变
attack
2018/04/11
6170
洛谷P4174 [NOI2006]最大获利
题目描述 新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。 在前期市场调查和站址勘测之后,公司得到了一共 N 个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第 i个通讯中转站需要的成本为  (1≤i≤N)。 另外公司调查得
attack
2018/04/11
7000
LOJ#505. 「LibreOJ β Round」ZQC 的游戏(最大流)
题意 题目链接 Sol 首先把第一个人能吃掉的食物删掉 然后对每个人预处理出能吃到的食物,直接限流跑最大流就行了 判断一下最后的最大流是否等于重量和 注意一个非常恶心的地方是需要把除1外所有人都吃不到的食物删掉 #include<bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 10, INF = 1e9 + 10; int sqr(int x) {return x * x;} inline int read() { char c
attack
2019/02/26
4240
洛谷P1345 [USACO5.4]奶牛的电信Telecowmunication
题目描述 农夫约翰的奶牛们喜欢通过电邮保持联系,于是她们建立了一个奶牛电脑网络,以便互相交流。这些机器用如下的方式发送电邮:如果存在一个由c台电脑组成的序列a1,a2,...,a(c),且a1与a2相连,a2与a3相连,等等,那么电脑a1和a(c)就可以互发电邮。 很不幸,有时候奶牛会不小心踩到电脑上,农夫约翰的车也可能碾过电脑,这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了,于是与这台电脑相关的连接也就不可用了。 有两头奶牛就想:如果我们两个不能互发电邮,至少需要坏掉多少台电脑呢?请编写一个程序
attack
2018/04/11
8180
洛谷P1345 [USACO5.4]奶牛的电信Telecowmunication
洛谷 P3386 【模板】二分图匹配 Dinic版
题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每行两个正整数u,v,表示u,v有一条连边 输出格式: 共一行,二分图最大匹配 输入输出样例 输入样例#1: 1 1 1 1 1 输出样例#1: 1 说明 n,m \leq 1000n,m≤1000, 1 \leq u \leq n1≤u≤n, 1 \leq v \leq m1≤v≤m 因为数据有坑,可能会遇到 v>mv>m 的情况。请把 v>mv>
attack
2018/04/11
7610
相关推荐
洛谷P4016 负载平衡问题(最小费用最大流)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验