费用流 类Dinic算法 费用流类Dinic算法 因为费用有负边权所以用spfa，求单位费用之和最小的路径 将bfs分层标记dep数组 换成 spfa分层标记dist[](最小费用和) dfs寻找多条增广路时, 开vis标记筛掉返回的边 ,且增广路顺着spfa标记的最小费用和路径走, dfs维护流和费用 Luogu P4016 注意: 环形, 最终n个仓库存货量相同, 只能在相邻的仓库之间搬运 建图 2019-11-03 算法 费用流
费用流 MCMF算法 Min cost Max flow算法Luogu P3381 实现思路 邻接表保存时注意： 费用具有对称性, 流量具有守恒性 spfa()根据边的容量\流量\花费来找到增广路, 以及维护每点的入边pre[i],和判断是否还有增广路 EK()路程: 已经通过了spfa()确定了增广路,第一次while找到增广路可以通过的最大流量, 第二次while()更新网络 维护maxflow和 2019-11-01 算法 费用流
HDU 1533 费用流入门 费用流 (最小费用最大流) 网络图中 每条边 多给出了 单位流量的费用 cost(u,v) ,当通过(u,v)的流量为$f(u,v)$时,需要花费 $f(u,v)*cost(u,v)$ 因为是在 最大流的前提下求出最小费用, 那么 最大流量已经确定了,即使每条边的花费不一样,但只要费用和最小就行了 EK+SPFA HDU 1533 人作为一部分,房子作为一部 2019-11-01 算法 费用流
差分数组 or 线段树 提交地址 描述: bbq的工作是管理学校的社团活动，具体来说是为每个社团活动分配教室。要把有限的教室合理安排给这些社团，是不容易的。每个社团活动用k, t1, t2来表示：该社团活动在第t1天～第t2天内需要k个教室（包括t1，t2）。bbq总是按社团活动申请的先后顺序分配教室，如果某一天剩余的教室数量不够满足某社团的要求，则停止教室的分配。bbq需要告知该社团，他们的该次社团活动无法进行。 2019-10-30 算法 差分数组
互斥和同步-读者/写者问题 读者/写者问题问题定义: 存在一个多进程共享的数据区,该数据区可以是 一个文件或者一块内存或者一组寄存器, 有些进程reader只读取该数据区中的数据, 有些进程writer只往数据区写数据 满足条件 任意数量的读进程可以同时读该文件 一次只有一个写进程可以写文件 若一个写进程正在写文件,则禁止任何进程读文件 综上即: 读进程不需要排斥其他进程,而写进程需要排斥其他所有进程 2019-10-30 操作系统 并发 同步
互斥和同步-消费者/生产者 (管程+消息传递) 管程 由一个或多个过程、一个初始化序列和局部数据组成的软件模块,主要特点: >1. 局部数据变量只能被**管程的过程**访问,任何外部过程都不能访问 >2. 一个进程通过调用**管程的一个过程**进入管程. >3. 只能有一个进程在管程中执行,调用管程的任何其他进程都被**阻塞**，以等待管程可用 管程的互斥机制: 管程的数据每次只能被一个进程访问 通过放入 共享 2019-10-29 操作系统 互斥 同步
互斥和同步-生产者/消费者问题 信号量解决互斥 由于所有进程都需要访问共享资源，每个进程进入临界区前执行 semWait(s),若s为负,则进程被阻塞,为正数则-1,进程立即进入临界区,由于s不为正,则其他任何进程不能进入临界区 下面将 缓冲区作为 共享资源 生产者/消费者问题 问题: 有一个或多个生产者生产某种类型的数据,放置在缓冲区,,有一个消费者从缓冲区取数据,每次取一项, 操作系统为了保证避免对缓冲区的重复 2019-10-28 操作系统 并发 互斥
简单shell脚本重启mysql服务 shell脚本定时检测mariadb状态,实现崩溃后重启服务 检测mysql状态多种方法（监听端口之类）, (centos7 systemctl中服务名称为mariadb也能用pgrep -x mysqld) 检测pgrep 命令返回值 然后重启服务 123456789# !/bin/bashtime=$(date)pgrep -x mysqld &> /dev/nulli 2019-10-27 Linux学习
HDU 1421 HDU 1421 刚开始的思路: 想到将所有物品重量的差求出来排序然后直接取出前m对最小的 忽略了 一个差代表2个个物品被取走了,那么其他包含这2个物品的差就应该消失,实现标记很困难 DP思路 先将所以重量排个序（那么每个物品的前后2个物品与此物品的差最小,注意到差值和物品重量大小无关） 状态dp[i][j]表遍历到到第i件物品, j 代表已经选了j对物品,dp[i][j]代表n件物品 2019-10-27 算法
php留言板小demo 测试环境 本地数据库名:php10 user:root,passwd: , 表:msg,4个字段id,content,user, intime 一些简单sql语句 增: INSERT INTO msg () VALUES (); 删: DELETE FROM msg WHERE id = 10; DELETE FROM msg 改: UPDATE msg SET content 2019-10-19 php 留言板