[BZOJ1221/Luogu2223][HNOI2001]软件开发

news/2024/4/15 4:32:12

题目链接:

BZOJ1221

Luogu2223

不是很好理解的费用流。

把每个点拆成两个点,一个早上(没用毛巾),一个晚上(用完毛巾)。

连边:

  • \(1.\)

早上与汇点连边,容量\(n_i\),费用\(0\),表示早上提供\(n_i\)条毛巾以供使用。

  • \(2.\)

源点与晚上连边,容量\(n_i\),费用\(0\),表示早上用剩下的毛巾。

  • \(3.\)

源点与早上连边,容量\(Inf\),费用\(f\),表示可以随便新买毛巾,一条\(f\)元。

  • \(4.\)

\(i\)不为最后一天,晚上与第二天晚上连边,容量\(Inf\),费用\(0\),表示可以不消毒,留着。

  • \(5.\)

\(i+a+1\le n\)(晚上用完第二天才开始消毒,所以\(+1\)),\(i\)天晚上向\(i+a+1\)天早上连边,容量\(Inf\),费用\(fa\),表示用\(A\)种消毒方式,可以在\(i+a+1\)天早上使用。

  • \(6.\)

\(5\)类似,消毒方式改为\(B\)

话说我的费用流好慢。。

#include <queue>
#include <cstdio>
#include <cstring>inline int Min(int a,int b){return a<b?a:b;}int n,a,b,f,fa,fb,St,Ed,MaxFlow,MinCost;
int Head[2005],Next[40005],To[40005],Val[40005],Cos[40005],En=1;
int Dis[2005],Pre[2005],Ref[2005],Inq[2005];
const int Inf=0x3f3f3f3f;inline void Add(int x,int y,int z,int w)
{Next[++En]=Head[x],To[Head[x]=En]=y,Val[En]=z,Cos[En]=+w;Next[++En]=Head[y],To[Head[y]=En]=x,Val[En]=0,Cos[En]=-w;
}bool SPFA()
{std::queue<int> q;memset(Dis,0x3f,sizeof Dis);q.push(St),Dis[St]=0,Ref[St]=1<<30;for(int x,y;!q.empty();q.pop(),Inq[x]=0)for(int i=Head[x=q.front()];i;i=Next[i])if(Val[i]&&Dis[y=To[i]]>Dis[x]+Cos[i]){Dis[y]=Dis[x]+Cos[Pre[y]=i];Ref[y]=Min(Ref[x],Val[i]);if(!Inq[y])Inq[y]=1,q.push(y);}if(Dis[Ed]==Inf)return false;MaxFlow+=Ref[Ed],MinCost+=Ref[Ed]*Dis[Ed];for(int x=Ed,i;x!=St;x=To[i^1])Val[i=Pre[x]]-=Ref[Ed],Val[i^1]+=Ref[Ed];return true;
}int main()
{scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);St=n<<1|1,Ed=St+1;for(int i=1,x;i<=n;++i){scanf("%d",&x);Add(i,Ed,x,0);Add(St,i+n,x,0);Add(St,i,Inf,f);if(i<n)Add(i+n,i+1+n,Inf,0);if(i+a+1<=n)Add(i+n,i+a+1,Inf,fa);if(i+b+1<=n)Add(i+n,i+b+1,Inf,fb);//6种连边如上所述}while(SPFA());printf("%d\n",MinCost);return 0;
}

转载于:https://www.cnblogs.com/LanrTabe/p/10210860.html


http://www.ppmy.cn/news/641513.html

相关文章

BZOJ 2223: [Coci 2009]PATULJCI

看题面戳我 因为给了上限&#xff0c;言外之意算法与数据的上限有关&#xff0c;猜测是数组&#xff0c;但想一想不可能&#xff0c;所以应该是权值线段树 综合一下&#xff0c;猜测应该是区间第K大&#xff0c;也就是主席树了 最暴力的做法&#xff1a;每次询问排序后查看是…

哈理工oj2223

水题 Time Limit: 500 MSMemory Limit: 32768 K Total Submit: 247(81 users)Total Accepted: 106(64 users)Rating: Special Judge: No Description 因为是有关于接水的问题&#xff0c;便简称为水题了&#xff08;。 N个人排队在M个出水口前接水&#xff0c;第i个人接水需时…

【bzoj2223】[Coci 2009]PATULJCI 主席树

题目描述 样例输入 10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10 样例输出 no yes 1 no yes 1 no yes 2 no yes 3 样例描述 第一行输入n和lim&#xff0c;为序列数的个数和数的范围&#xff08;1≤a[i]≤lim&#xff09; 第二行输入n个数。 第三行输入m&#…

Hrbust2223水题

水题 Time Limit: 500 MSMemory Limit: 32768 K Total Submit: 248(82 users)Total Accepted: 106(64 users)Rating: Special Judge: No Description 因为是有关于接水的问题&#xff0c;便简称为水题了&#xff08;。 N个人排队在M个出水口前接水&#xff0c;第i个人接水需时…

【bzoj3524/2223】[Poi2014]Couriers/[Coci 2009]PATULJCI 主席树

Description 给一个长度为n的序列a。1≤a[i]≤n。 m组询问&#xff0c;每次询问一个区间[l,r]&#xff0c;是否存在一个数在[l,r]中出现的次数大于(r-l1)/2。如果存在&#xff0c;输出这个数&#xff0c;否则输出0。 Input 第一行两个数n&#xff0c;m。 第二行n个数&…

bzoj2223 [Coci 2009]PATULJCI

http://www.elijahqi.win/archives/1717 Description Input Output 10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10 Sample Input no yes 1 no yes 1 no yes 2 no yes 3 Sample Output HINT Notice:输入第二个整数是序列中权值的范围Lim&#x…

2223c语言学习日记

一、变量的作用域和生命周期 int main(); { int var 10; printf("%d\n", var); return 0; } 作用域&#xff1a;一个变量只能在它所在的中括号内有效。 生命周期&#xff1a;一个变量的从作用到销毁的时间段。即中括号内的工作时间。 绿框内即var的作用域&am…

P2223 [HNOI2001]软件开发

题目 题目 思路 HN省选&#xff08;海南&#xff1f;湖南&#xff1f;河南&#xff1f;&#xff09;出重题…… where’re your faces? 这里只需要把明天改成今天即可。 code&#xff1a; #include<iostream> #include<cstdio> #include<algorithm> #in…

bzoj2223[Coci 2009] PATULJCI

题目链接&#xff1a;bzoj2223 题目大意&#xff1a; 给一个N个数的序列&#xff0c;M次询问&#xff0c;每次询问一个区间[l,r]内是否有某个数出现次数大于(r-l1)/2&#xff0c;如果存在则输出这个数&#xff0c;否则输出no。 题解&#xff1a; 整体二分 二分答案mid&#xff…

hrbust 2223 水题

水题 Time Limit: 500 MSMemory Limit: 32768 K Total Submit: 321(108 users)Total Accepted: 133(83 users)Rating: Special Judge: No Description 因为是有关于接水的问题&#xff0c;便简称为水题了&#xff08;。 N个人排队在M个出水口前接水&#xff0c;第i个人接水需时…

hnust 2223: 最长回文数的位数

这题其实并不是很复杂&#xff0c;给一组0-9的数据&#xff0c;求回文长度&#xff0c;首先我们要知道回文左右的数是相同的&#xff0c;要求最长&#xff0c;我们可以把0-9出现的次数记录下来&#xff0c;有两种情况&#xff0c;出现次数是否为偶数&#xff0c;如果是偶数的话…

leetcode 2223 — 构造字符串的总得分和

leetcode 2223 — 构造字符串的总得分和 一、题目描述二、算法1、泛化问题描述2、分析3、实现 一、题目描述 二、算法 这道题实际上就是考察的Z 算法。 1、泛化问题描述 对于个长度为 n n n 的字符串 s s s。定义函数 z [ i ] z[i] z[i] 表示 s s s 和 s [ i : n − 1 ]…

C语言错误c2223是什么错误,C语言链表:报错error:c2223 “-next”的左侧必须指向结构/联合...

今天用vs2013练习C语言&#xff0c;链表创建输出。但是碰到一个问题error&#xff1a;c2223 “->next”的左侧必须指向结构/联合。我想了一上午都没想明白&#xff0c;到开源中国和吾爱发完求助帖准备先睡一觉。突然试了编译一下&#xff0c;没有错误了。先上源代码。 错误代…

go系列-base64加密与解密

1 标准编码与解码 package mainimport ("encoding/base64""fmt" )func main() {var str string "杨国强"//标准加密encoded : base64.StdEncoding.EncodeToString([]byte(str))fmt.Printf("str:%v\n", encoded)//标准解密decoded, e…

实训笔记6.29

实训笔记6.29 6.29一、座右铭二、批量数据操作三、JavaBean与数据库中的数据表四、 JDBC实现事务操作五、封装JDBC工具类六、数据库连接池6.1 连接池6.2 动态代理模式 七、单元测试 6.29 一、座右铭 我的故事你说&#xff0c;我的文字我落&#xff0c;我值几两你定&#xff0…

诺基亚7plus支持html,【诺基亚7Plus评测】外观:全面屏是最大亮点_诺基亚 7 Plus(4GB RAM/全网通)_手机评测-中关村在线...

外观&#xff1a;全面屏是最大亮点 总的来看&#xff0c;诺基亚 7 Plus拥有和诺基亚 7类似的设计语言&#xff0c;无论是机身右上角的“NOKIA”logo还是机身背后的摄像头布局&#xff0c;诺基亚 7 Plus与诺基亚 7一脉相承。 但是细看之下&#xff0c;诺基亚 7 Plus相较于诺基亚…

诺基亚7plus支持html,【诺基亚7Plus评测】屏幕:LCD阵营上游水平_诺基亚 7 Plus(4GB RAM/全网通)_手机评测-中关村在线...

屏幕&#xff1a;LCD阵营上游水平 屏幕方面&#xff0c;诺基亚 7 Plus搭载的一块6英寸18&#xff1a;9的LCD全面屏&#xff0c;分辨率为1080P。 我们选择在全黑封闭环境下进行测试&#xff0c;手机中安装DisplayTester Pro屏幕亮度调最高&#xff0c;关闭屏幕自动休眠&#xff…

诺基亚7原生android,【诺基亚7Plus评测】系统:简洁原生安卓功能却不简单_诺基亚 7 Plus(4GB RAM/全网通)_手机评测-中关村在线...

系统&#xff1a;简洁原生安卓功能却不简单 诺基亚 7 Plus的系统为Android 8.0&#xff0c;与国内厂商大刀阔斧的定制化相反&#xff0c;诺基亚 7 Plus的系统几近原生&#xff0c;仅仅内置了微信、微博、支付宝三款国民应用&#xff0c;而且这三个软件都可以卸载&#xff0c;最…

SmaAt-UNet github

来源 SmaAt-UNet github SmaAt-UNet&#xff1a; 使用小型关注网结构的降水预报 论文链接 安装依赖 这个项目使用poetry作为依赖性管理。因此&#xff0c;安装所需的依赖项就像这样简单&#xff1a; conda create --name smaat-unet python3.9 conda activate smaat-unet p…

HarmonyOS开发详解(二)——鸿蒙开发体系详解及入门实例演示运行

本篇文章的计划&#xff0c;先体系的介绍一下鸿蒙开发相关的体系内容&#xff0c;希望通过本篇内容构建对鸿蒙开发体系的了解&#xff0c;最后再来一个最简单入门例子。既是自我的学习&#xff0c;也希望对你了解鸿蒙开发的全貌有帮助。 这样安排而没有直接写一个Helloworld例子…
最新文章