781 字 1 分钟

# 背景 给定一个 nnn 个点 mmm 条边的有向图，图中可能存在 重边 和 自环，边权可能为负数 再给定 kkk 个询问，每个询问包含两个整数 xxx 和 yyy，表示查询从点 xxx 到点 yyy 的最短距离，如果路径不存在，就输出 impossible # 思路 FloydFloydFloyd 本质上是动态规划，通过三层循环分别枚举中间点、起点、终点，暴力求解 利用二维数组存图 d[起点][终点] = min(d[起点][终点], d[起点][中间点] +...
2k 字 2 分钟

# Spfa 求最短路 # 背景 给定一个 nnn 个点 mmm 条边的有向图，图中可能存在重边和自环，边权可能为负数 请你求出 111 号点到 nnn 号点的最短距离，如果无法从 111 号点走到 nnn 号点，则输出 impossible 数据保证不存在负权回路 # 数据范围 1≤n,m≤1051 \le n,m \le 10^51≤n,m≤105 # 思路 利用邻接表存图，队列操作 如果当前到 j(e[i]) 点的步数小于遍历时，先去 d[t] 点再去 j(e[i]) 点的步数，则更新 d[j] 的值 如果此时， j(e[i])...
1.2k 字 1 分钟

# 背景 给定一个 nnn 个点 mmm 条边的有向图，图中可能存在重边和自环，边权可能为负数 请你求出 111 号点到 nnn 号点的，最多经过 kkk 条边的最短距离，如果无法从 111 号点走到 nnn 号点，输出 impossible # 数据范围 1≤n,k≤5001 \le n, k \le 5001≤n,k≤500 1≤m≤100001 \le m \le 100001≤m≤10000 1≤x,y≤n1 \le x, y \le n1≤x,y≤n # 思路 用结构体记录路径，经历 kkk 次循环，每次循环都对 d[i]...
584 字 1 分钟

# 拓扑排序的概念 拓扑排序要解决的问题是如何给一个有向无环图的所有节点排序 在一个 DAGDAGDAG （有向无环图）中，将图中的顶点以线性方式进行排序，使得对任何顶点 uuu 到 vvv 的有向边 (u,v)(u,v)(u,v)，都有 uuu 在 vvv 前面 # Kahn 算法求拓扑排序 利用队列求解，不断把入度为 000 的点推入队列，每次从队列中取出一个，对于该点能到的所有边，减去到的点的入度，如果又到 000 了的话，则继续推入队列，直到队列空为止 C++123456789101112131415161718192021222324void solve ()...
6.7k 字 6 分钟

# KMP 算法的定义 KMPKMPKMP 算法常用于在一个文本串 SSS 内查找一个模式串 PPP 出现的位置，算法流程如下： 假设现在文本串 SSS 匹配到 iii 位置，模式串匹配到 jjj 位置： 如果 j = -1 ，或者当前字符匹配成功（ s[i] == p[j] ），都令 i++, j++ ，然后继续匹配下一个字符 如果 j != -1 ，并且当前字符匹配失败（ s[i] != p[j] ），则令 iii 不变， j = next[j] 。此操作意味着当匹配失败时，模式串 PPP 相对于文本串 SSS 向右移动了 j - next[j] 位 # next...
3k 字 3 分钟

# 题目大意 一个车间有 nnn 台设备，构成以 111 为根结点的一棵树，结点 iii 有权值 wiw_iwi​ 叶节点的权值 wiw_iwi​ 表示每单位时间将产出 wiw_iwi​ 单位的材料并送往父结点 根结点的权值 wiw_iwi​ 表示每单位时间内能打包多少单位成品 其他结点的权值 wiw_iwi​ 表示每单位时间最多能加工 wiw_iwi​ 单位的材料并送往父结点。 由于存在某些结点每单位时间收到的材料超过了当前结点的加工能力上限，现计划删除一些结点使得所有结点都能正常运行 请问删除一些结点后，根结点每单位时间内最多能打包多少单位的成品？ # 数据范围 对于...
687 字 1 分钟

# 题目大意 有 nnn 组物品和一个容量 vvv 的背包，每组物品有若干个，同一组内的物品最多只能选一个 每件物品的体积是 vi,jv_{i,j}vi,j​，价值是 wi,jw_{i,j}wi,j​，其中 iii 是组号，jjj 是组内编号 求解，能装下的最大体积是？ # 数据范围 0<N,V≤1000 < N,V \le 1000<N,V≤100 0<Si≤1000 < S_i \le 1000<Si​≤100 0<vi,j,wi,j≤1000 <...
1.3k 字 1 分钟

# 题目大意 有 nnn 种物品和一个容量是 vvv 的背包 第 iii 种物品的体积是 viv_ivi​，价值是 wiw_iwi​，有 sis_isi​ 件 问：你放进背包的最大价值是多少 # 数据范围 小范围（多重背包 III） 0<N,V≤10000 < N, V \le 10000<N,V≤1000 0<vi,wi≤10000 < v_i, w_i \le 10000<vi​,wi​≤1000 大范围（多重背包 IIIIII） 0<N≤10000 <...
1.3k 字 1 分钟

# 题目大意 有 nnn 种物品和一个容量是 vvv 的背包，每种物品都有无限件 第 iii 种物品的体积是 viv_ivi​，价值是 wiw_iwi​ 问：你放进背包的最大价值是多少 # 数据范围 0<N,V≤10000 < N, V \le 10000<N,V≤1000 0<vi,wi≤10000 < v_i, w_i \le 10000<vi​,wi​≤1000 # 思路 显然可以借鉴 010101 背包的思路， dp[i][j] 表示选到第 iii 个物品，背包容量为 jjj...