死锁和饥饿-哲学家就餐问题
哲学家就餐问题 背景: 假设5位哲学家住在一起(可以推广到n),每天生活就是思考和吃饭,每位哲学家需要2把叉子来吃意大利面. 就餐安排: 一张圆桌,5个板凳,5个盘子,5把叉子,每个想吃饭的哲学家做到椅子上,使用盘子2侧的叉子来吃面条, 问题: 设计算法 保证互斥(2位哲学家不能使用相邻的叉子),同时还要避免死锁(每个哲学家都在等待叉子,且占用了叉子)和饥饿 信号量解决方案 规定: 每
emerald's blog
费用流 类Dinic算法
费用流类Dinic算法 因为费用有负边权所以用spfa，求单位费用之和最小的路径 将bfs分层标记dep数组 换成 spfa分层标记dist[](最小费用和) dfs寻找多条增广路时, 开vis标记筛掉返回的边 ,且增广路顺着spfa标记的最小费用和路径走, dfs维护流和费用 Luogu P4016 注意: 环形, 最终n个仓库存货量相同, 只能在相邻的仓库之间搬运 建图 将流量看做在仓库
费用流 MCMF算法
Min cost Max flow算法Luogu P3381 实现思路 邻接表保存时注意： 费用具有对称性, 流量具有守恒性 spfa()根据边的容量\流量\花费来找到增广路, 以及维护每点的入边pre[i],和判断是否还有增广路 EK()路程: 已经通过了spfa()确定了增广路,第一次while找到增广路可以通过的最大流量, 第二次while()更新网络 维护maxflow和max
HDU 1533 费用流入门
费用流 (最小费用最大流) 网络图中 每条边 多给出了 单位流量的费用 cost(u,v) ,当通过(u,v)的流量为$f(u,v)$时,需要花费 $f(u,v)*cost(u,v)$ 因为是在 最大流的前提下求出最小费用, 那么 最大流量已经确定了,即使每条边的花费不一样,但只要费用和最小就行了 EK+SPFA HDU 1533 人作为一部分,房子作为一部分， 费用是坐标系下的距离,
差分数组 or 线段树
提交地址 描述: bbq的工作是管理学校的社团活动，具体来说是为每个社团活动分配教室。要把有限的教室合理安排给这些社团，是不容易的。每个社团活动用k, t1, t2来表示：该社团活动在第t1天～第t2天内需要k个教室（包括t1，t2）。bbq总是按社团活动申请的先后顺序分配教室，如果某一天剩余的教室数量不够满足某社团的要求，则停止教室的分配。bbq需要告知该社团，他们的该次社团活动无法进行。 i
互斥和同步-读者/写者问题
读者/写者问题问题定义: 存在一个多进程共享的数据区,该数据区可以是 一个文件或者一块内存或者一组寄存器, 有些进程reader只读取该数据区中的数据, 有些进程writer只往数据区写数据 满足条件 任意数量的读进程可以同时读该文件 一次只有一个写进程可以写文件 若一个写进程正在写文件,则禁止任何进程读文件 综上即: 读进程不需要排斥其他进程,而写进程需要排斥其他所有进程
互斥和同步-消费者/生产者 (管程+消息传递)
管程 由一个或多个过程、一个初始化序列和局部数据组成的软件模块,主要特点: 123>1. 局部数据变量只能被**管程的过程**访问,任何外部过程都不能访问 >2. 一个进程通过调用**管程的一个过程**进入管程. >3. 只能有一个进程在管程中执行,调用管程的任何其他进程都被**阻塞**，以等待管程可用 管程的互斥机制: 管程的数据每次只能被一个进程访问 通过放入 共享数据
互斥和同步-生产者/消费者问题
信号量解决互斥 由于所有进程都需要访问共享资源，每个进程进入临界区前执行 semWait(s),若s为负,则进程被阻塞,为正数则-1,进程立即进入临界区,由于s不为正,则其他任何进程不能进入临界区 下面将 缓冲区作为 共享资源 生产者/消费者问题 问题: 有一个或多个生产者生产某种类型的数据,放置在缓冲区,,有一个消费者从缓冲区取数据,每次取一项, 操作系统为了保证避免对缓冲区的重复