首页 > 其他分享 >餐巾计划问题

餐巾计划问题

时间:2023-11-17 13:15:37浏览次数:29  
标签:表示 餐巾 恰好 问题 计划 天往 inf 起点

餐巾计划问题

先拆点,将每天拆成两个点,一个表示用完的旧餐巾①,一个表示需要的新餐巾②。

考虑几种边:

  1. 购买边,从起点往②点连 \(\inf,p\)。
  2. 快洗边,从前 \(m\) 天往②点连 \(\inf,p\)。
  3. 慢洗边,从前 \(n\) 天往②点连 \(\inf,f\)。
  4. 容量限制边
    1. 从②点往终点连 \(r_i,0\) 的边。(表示只接受 \(r_i\) 条)
    2. 从起点往①连 \(r_i,0\) 的边。(表示每天恰好用完 \(r_i\) 条)

发现最大流对应恰好用完的情况,跑最小费用最大流即可。

code

标签:表示,餐巾,恰好,问题,计划,天往,inf,起点
From: https://www.cnblogs.com/wscqwq/p/17636972.html

相关文章

  • 分配问题
    分配问题考虑到类似于飞行员配对问题,唯一区别就是多了一个费用,跑费用流即可。注意最长路的求法就是最短路的边权全部变成负的,然后最后负回来。code......
  • 运输问题
    运输问题将超级源和左边的点连\(a_i\),右边的点和超级汇连\(b_j\),中间并没有规定只能给多少货物,设为无穷大。然后就类似于分配问题。code......
  • 负载平衡问题
    负载平衡问题看看就算了,注意\(X_i\)的定义最后一项应该是\(\sum\limits_{j=1}^{i}A_j\)而不是\(\sum\limits_{j=1}^{i-1}A_j\)。code......
  • 常见问题
    在python中,什么是生成器,什么是迭代器,他们的区别是什么生成器是一种特殊类型的函数,它使用`yield`语句来产生一个序列的值。生成器函数在每次调用时返回一个生成器对象,可以通过调用生成器对象的`__next__()`方法来逐个获取生成器产生的值。生成器可以通过循环或使用`next()`函数来......
  • MySQL中使用范围查询后索引失效问题
    假设我们为表table的a,b,c三列创建了联合索引createindexidx_a_b_contable(a,b,c),并且在B+树中,数据的存储顺序如下:(a=1b=1c=1)(a=1b=2c=1)(a=1b=2c=3)(a=2b=2c=3)(a=2b=2c=5)(a=2b=5c=1)(a=2b=5c=2)(a=3b=0c=1)(a=3b=3c=5)(a=3b=8c=6)使用查询......
  • sql server 备份还原 版本一致性问题
      SELECT@@VERSIONAS'SQLServer版本号'......
  • IIS中SSL证书过期更新的问题
    小程序访问后端接口报超时错: 查看证书已过期,如下:更新证书步骤如下:云服务器上下载最新有效期内证书: 下载下来的是压缩包,里面包含一个证书文件*.pfx和一个密钥文件*.txt,复制到服务器上备用。打开IIS服务管理器,点击计算机名称,双击‘服务器证书’ 双击打开服务器证书后......
  • HCS651统一备份FusionSphere备份失败问题小结
    登录ELB-DB节点在确认查询无网络问题后此节点从失败详情中能够查询到,主备IP可根据详情中的IP地址关联从om获取 #cat/etc/sudoers.d/elbommALL=(root)NOPASSWD:/opt/gaussdb/ha/tools/gsCerts/query_gs_ca.shommALL=(root)NOPASSWD:/opt/gaussdb/ha/tools/gsCerts/qu......
  • 签题补完计划
    手贱让cnblogs这小崽子给我把发布时间更新了。实际上这篇文章很早就存在,只是一直没有公开而已。从现在开始,因为现在我手上刚好有一道水题可以用来凑数!!!......
  • go语言解决跨域的问题图片显示问题
    来源:http://www.shanhubei.com/archives/2838.html直接上代码packagemainimport("fmt""io/ioutil""net/http")//获取C的图片数据funcReadImgData(urlstring)[]byte{resp,err:=http.Get(url)iferr!=nil{......