Texcavator 的秘密基地

数字三角形题目在这里 题目给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输入格式 第一行包含整数 n，表示数字三角形的层数。 接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。 输出格式 输出一个整数，表示最大的路径数字和。 数据范围 1 ≤ n ≤ 500,−10000 ≤ 三角形中的整数 ≤ 10000 输入样例573 88 1 0 2 7 4 44 5 2 6 5 输出样例30 解法每个点只可能从左上方点 or 右上方点走过来，所以在这 ...

理论基础什么是连通分量？ 对于一个有向图，分量中任意两点u，v，必然可以从u走到v，且从v走到u，这样的分量叫做连通分量 如果一个连通分量加上任意一个点都不是连通分量了，就把它叫做 强连通分量 强连通分量的主要作用：将任意一个有向图转化成一个有向无环图即拓扑图（通过缩点的方式），缩点就是将所有连通分量缩成一个点 如何求强连通分量呢？ 按照DFS的顺序搜，我们可以将边分为以下四类： 树枝边：(x, y)，x是y的父结点 前向边：(x, y)，x是y的祖先结点 后向边：(x, y)，y是x的祖先结点 横叉边：往之前搜过的其他点搜 怎么判断一个点是否在强连通分量中？ 情况一：存在后向边指向祖先结点 情况二：先走到横叉边，横叉边再走到祖先结点 （反正一定可以走到某个祖先） 基于这个想法—— ==Tarjan== 算法求强连通分量（SCC） 先给每个结点按照 DFS 访问顺序确定一个时间戳，时间戳越小说明越先访问到 dfn[u]：遍历到 u 的时间戳low[u]：从 u 开始走，能遍历到的最小时间戳id[i]：i 所在连通分量的编号 u是其所在强连通分量的最高点 <-> df ...

基本方法Kruskal算法步骤与基本思路（1）初始化所有点，每个点单独在一个点集。把所有边按权重排序 （2）按边权重从小到大遍历每一条边，如果这条边的两个顶点不在同一个点集，就将它们加到同一点集，也就是选中这条边，以此类推 （3）如果最后加入同一个点集的点个数小于n个说明这个图不是连通图，无法生成最小生成树 Kruskal板子struct Edge{ int a, b, w; bool operator< (const Edge &W) const { return w < W.w; }}edges[M];int find(int x) // 判断x属于哪一个点集{ if (x != p[x]) p[x] = find(p[x]); return p[x];}int kruskal(){ sort(edges, edges + m); // 所有边按权重排序 for (int i = 1; i <= n; i ++ ) p[i] ...

单源最短路的建图方式最短路问题可以分为以下两类： 边权非负——朴素Dijkstra、堆优化Dijkstra 有负权边——Bellman-Ford、SPFA 例题热浪原题链接 德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！ 他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。 农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。 John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。 这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。 除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。 每条道路有一个通过费用（包括油费，过路费等等）。 给定一个地图，包含 C 条直接连接 2 个城镇的道路。 每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。 求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。 输入格式 第一行: 4 个由空格隔开的整数: T,C,Ts,Te; 第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路，包含 3 个由空 ...

1、Dijkstra算法不能处理边权为负的情况，复杂度O(nlogn) 步骤与基本思路（1）初始化距离数组dist[N]，将其所有值赋为0x3f，并将起点1的dist初始化为0，存入优先队列heap中 （2）从所有未被遍历的点中找到与起点1的距离dist[i]最小的点，并将该点标记为已遍历 （3）利用刚刚遍历的这个点 i 更新所有 i 的出边所连的点与起点1的距离，更新后存入heap中 （4）重复操作（2）（3）直至heap空 Dijkstra板子int dijkstra() // 返回起点到终点的距离{ memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // first为dist second为具体的点 while (heap.size()) { auto t = heap.t ...