网络流初步 （寒假集训听了听i207M学长的课，感觉收获颇丰啊 定义 老样子，先从定义开始： 网络：网络是指一个有向图，G=(V,E)G=(V,E)G=(V,E)，V是点集，E是边集，对于任意的(u,v)∈V(u,v)\in V(u,v)∈V，都对应的有一个边权，这个边权代表一个限制性的东西，我们称之为容量。我们定义一条边属于一个网络里，有且仅有...

花了 3-4 天的时间干掉了这个算法：tarjan（虽然只是干掉了板子） 有向图 我刚开始学了一天的无向图，看懂了板子之后，机房大佬告诉我先学有向图的比较好……然后就开始学有向图…… 有向图 tarjan 的内容比较少，只有强连通分量，缩点，必经点和必经边 前置定义 给定一个有向图，如果在这个有向图中存在一个点，从它出发可以到达图中所有的点，那么称...

Tree 洛谷 P2619 一道生成树的很好的题目 题目描述 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 need 条白色边的生成树。 乍一看还是很没有头绪的（反正刚开始我没有 思路 由于我们需要求一个最小权的，恰好有 need 条边的生成树 首先可以想到一个贪心的作法就是我先把最小的白边加入生成树之中直到 need 条跑...

MST 最小生成树板子 前言 今天对我的图论知识进行了一次的扩充，最小生成树 前言知识：并查集，可以去翻我的博客虽然还不完善但也有一点点的用途 kruskal 算法 思路 kruskal 算法由 kruskal 发明（废话），本质思想是在两个最小联通块之间找到最小的边使得这两联通快之间合并代价最小（就是边权 所以，kruskal 算法是一个贪心的做...

并查集 前言 今天根据书上的指引，想要学习最小生成树，然而蒟蒻在 OI WIKI 上学习的时候被告知： 前置章节是并查集。。。 于是蒟蒻便用了一天的时间 A 了三道黄题一道蓝题（其实相当于一道黄题…… 所以今天蒟蒻过来总结一番 定义 并查集是一种树形结构，通过名字我们可以知道： 并：合并，查：查询，集：集合 就是合并和查询一个集合 也可以相当于是联...

最近公共祖先 LCA 洛谷 P3379 今天 xiao 习了一下 LCA 过程十分曲折。。。 （检查的时候主函数没有调用 dfs，调试了好几遍才发现。。。 首先，我们先来看一看定义：最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 它有三种做法： 暴力 ...

P1827 奶牛 题目解读 其实说到底就是一道树的后序遍历反推而已嘛 首先，让我们看一遍题目： 给了一棵树的前序中序遍历，让求出后序遍历；（习惯性的打出分号 https://oi-wiki.org/graph/tree-basic/#_14（附上OI-WIKI的讲解 首先我们知道前序遍历在开头是根节点，那么，就将根节点取出（用 string 可做到...