查询GPIO状态值(步骤）1.导出GPIO（如果还没有被导出）： echo 31 > /sys/class/gpio/export 2.查询是否导出成功 ls -lh /sys/class/gpio/gpio31 如果出现gpio31文件夹，说明gpio导出成功。开机时导出一次即可 3.查…

最长路（topsort+DP算法） 计算一张 \(\tt DAG\) 中的最长路径，在执行前可能需要使用 \(\tt tarjan\) 重构一张正确的 \(\tt DAG\) ，复杂度 \(\mathcal O(N+M)\) 。 struct DAG {int n;vector<vector<pair<…

最短路径树（SPT问题）定义：在一张无向带权联通图中，有这样一棵生成树：满足从根节点到任意点的路径都为原图中根到任意点的最短路径。 性质：记根节点 \(Root\) 到某一结点 \(x\) 的最短距离 \(dis_{Root,x}\) ，在…

欧拉路径/欧拉回路 Hierholzers欧拉路径：一笔画完图中全部边，画的顺序就是一个可行解；当起点终点相同时称欧拉回路。有向图欧拉路径存在判定 有向图欧拉路径存在：\(\tt ^1\) 恰有一个点出度比入度多 \(1\) （为起点…

无源汇点的最小割问题 Stoer–Wagner也称为全局最小割。定义补充（与《网络流》中的定义不同）： 割：是一个边集，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）。通过递归的方式来解决无向正权图上的全…

染色法判定二分图 (dfs算法) 判断一张图能否被二分染色。 vector<int> vis(n + 1); auto dfs = [&](auto self, int x, int type) -> void {vis[x] = type;for (auto y : ver[x]) {if (vis[y] == type) {…

链式前向星建图与搜索 很少使用这种建图法。\(\tt dfs\) ：标准复杂度为 \(\mathcal O(N+M)\)。节点子节点的数量包含它自己（至少为 \(1\)），深度从 \(0\) 开始（根节点深度为 \(0\)）。\(\tt bfs\) ：深度从 \(1\) …

一般图最大匹配（带花树算法） 与二分图匹配的差别在于图中可能存在奇环，时间复杂度与边的数量无关，为 \(\mathcal O(N^3)\) 。下方模板编号从 \(0\) 开始，例题为 UOJ #79. 一般图最大匹配 。 struct Graph {int n;…