标签:算法学习

4 篇文章

EK (Edmond-Karp) 算法 学习笔记
什么是EK算法 EK (Edmond-Karp) 算法,说白了就是求最大流/费用流之类的问题的算法。 什么是最大流 定义 带权的有向图$G=(V,E)$,满足以下条件,则称为网络流图$(flow network)$: 仅有一个入度为$0$的顶点$s$,称$s$为源点。仅有一个出度为$0$的顶点$t$,称$t$为汇点。每条边的权值都为非负数,称为该边…
树链剖分 算法学习
树你应该懂的吧o( ̄︶ ̄)o 学习树链剖分之前需要先学习:$dfs$、线段树(当然大佬们用树状数组代替线段树也可以O(∩_∩)O),据说一名普及+的$oier$应该都会呀 先来了解树链剖分的用处 Luogu题目传送门 已知一棵包含$N$个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从…
博弈论之威佐夫博弈 算法学习
博弈论之威佐夫博弈 威佐夫博弈(Wythoff's game)是指的这样一个问题:有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。 ——转自百度百科 就比如洛谷的P2252 取石子游戏就是威佐夫博弈的裸题。。。 威佐夫博弈的性质 首先,由题目可知,当这两堆石子一样…
缩点求强连通分量——Kosaraju算法 学习笔记
Kosaraju 算法学习 序 这星期捣鼓了一个新的算法——Kosaraju算法 今天分享给大家 简介 Kosaraju算法,其实与tarjan算法差不多。但是码量较小,容易记忆。其时间复杂度与tarjan算法一样,为O(n+m),所以,某种程度上来说Kosaraju可以替代tarjan算法。 算法思路 如果直接让我讲Kosaraju算法到底是基于…