最小割 基础模型：构筑二分图，左半部 \(n\) 个点代表盈利项目，右半部 \(m\) 个点代表材料成本，收益为盈利之和减去成本之和，求最大收益。 建图：建立源点 \(S\) 向左半部连边，建立汇点 \(T\) 向右半部连边，如果某…

费用流 给定一个带费用的网络，规定 \((u,v)\) 间的费用为 \(f(u,v) \times w(u,v)\) ，求解该网络中总花费最小的最大流称之为最小费用最大流。总时间复杂度为 \(\mathcal O(NMf)\) ，其中 \(f\) 代表最大流。 struct…

图论常见结论及例题 常见结论要在有向图上求一个最大点集，使得任意两个点 \((i,j)\) 之间至少存在一条路径（可以是从 \(i\) 到 \(j\) ，也可以反过来，这两种有一个就行），即求解最长路；要求出连通图上的任意一棵生…

查询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也称为全局最小割。定义补充（与《网络流》中的定义不同）： 割：是一个边集，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）。通过递归的方式来解决无向正权图上的全…