日记详情

CF1245D

• 死因：一开始想虚点去了，但是想不出来，后来考虑了两个点之间合法的方案，近似推出了结论，但是没有结合 kruskal 和连通块。

两种做法，一种 kruskal，还有一种建超级源点！

kruskal 考虑从小到大加入边，两个连通块 \(S ,T\)，记当前边权为 \(w(S ,T)\)，\(cost_S = \sum_{i \in S} c_i\)，建电缆代价为 \(\min\{ cost_S , cost_T \} + w(S ,T) + \dots\)，不建电缆代价为 \(cost_S + cost_T + \dots\)，\(\dots\) 为连通块内所有边权之和，可以得到建电缆当且仅当 \(w(S ,T) \le \max\{cost_S ,cost_T\}\)，否则不建电缆。然后合并连通块 \(S ,T\)。

第二种是建超级源点 \(n + 1\)，连边 \(\forall 1\le i\le n ,(n + 1 ,i ,c_i)\)，跑 kruskal 最小生成树。

CF938D

• 死因：纯唐。

• 考虑一种错误的建模，给每个点开一个虚点 \(i'\)，连接 \((i ,i' ,a_i)\)，再开虚点 \(i''\)，连接 \((i' ,i'' ,0)\)，对于 \(\forall (u ,v ,w) \in E\)，连边 \((u'' ,v'' ,w)\)，题意转化为对于每个 \(i\) 求 \(i ,i''\) 的最短路，你发现无法跑多源 dij。

好了唐死了。

正确解法是开一个超级虚点 \(x\)，连边 \((x ,i ,a_i)\)，处理点权；我们想要单源 dij 因此要从 \(x\) 出发，因此对于边 \((u ,v ,w)\)，处理返程只要改为 \((u ,v ,2w)\)，然后做完了。

CF51E

五元环计数？！强强？！

哦原来是 \(n \le 700\)。

• 死因：还没做到就讲了。

两种思路。

第一种考虑一个五元环 \(a \to b \to c \to d \to e\)，若在 \(a\) 点计数，\(n \le 700\) 并且 \(10s\) 的宽裕时限允许我们枚举两个点，不妨枚举 \(c ,d\)，此时要求 \(a,c\) 以及 \(d ,a\) 间都有长度为 \(2\) 的路径，并且 \(c ,d\) 有直接路径，记 \(i ,j\) 间路径长度为 \(2\) 有 \(f_{2 ,i ,j}\) 条，方案数为 \(f_{2 ,a ,c} \times f_{2 ,a ,d}\)，有两种情况会算重。

一种是 \(a ,d\) 或 \(a ,c\) 之间有之间连边，那么 \(f_{2 ,a ,c} / f_{2 ,a ,d}\) 会多算一种且这种显然不能构成五元环，那么改为加上 \((f_{2 ,a ,c} - e_{a ,d}) \times (f_{2 ,a ,d} - e_{a ,c})\)，若 \(i ,j\) 有直接连边则 \(e_{i ,j} = 1\)。

另一种是三元环 \(a \to b \to c\) 并且 \(a / b /c\) 上挂有其余点，比如 \(a \to x\)。

在节点 \(x\) 处，\(f_{2 ,x ,b} = f_{2 ,x ,c} = 1\)，当枚举到点对 \((x ,b ,c)\) 和 \((x ,c ,b)\) 时会多算 \(1\)，总共多算 \(2\)。

考虑删去它的贡献，当枚举到一个三元环 \((a ,b ,c)\) 和 \((a ,c ,b)\) 时，多余连边数量即为多算贡献，减去 \(deg_a - 2\) 即可，这里 \(deg_a\) 为 \(a\) 的度。

多余贡献减完，五元环每个点会对一个五元环产生一个贡献，两个绕环方向又多一倍贡献，因此输出 \(ans \div (5\times 2) = ans \div 10\)。

---

第二种思路比较新奇，设 \(f_{k ,i ,j}\) 为 \(i\) 经过 \(k\) 条边到达 \(j\) 的方案数，五元环数量（包括算错/重的）即为 \(ans = \sum f_{5 ,i ,i}\)，令 \(ans \gets ans \div 10\)，感性理解五元环是这样，其余的被当作五元环结构也会算成原来的 \(10\) 倍，现在除了错误外没有重复。

这时在三元环子结构会算重，考虑枚举本质不同的三元环 \(a ,b ,c\)，会多算个数。

如图，\(x ,y ,w ,z\) 分别会多算一个，减去 \(deg_a + deg_b + deg_c - 6\)；\(a ,b ,c\) 分别会多算一个不合法的（\(c \to a \to c \to a \to b \to c\)，\(b \to c \to b \to c \to a \to b\)，\(a \to b \to a \to b \to c \to a\)，也就是一种错误的环上的边每条都经过两次），新增 \(3\) 个，总共减少 \(deg_a + deg_b + deg_c - 3\) 个，做完了。

P3953

• 死因：还没做就讲了，这个状态想到了但是转移 & 转移顺序想不到。

注意到 \(k\) 很小，显然状态 \(f_{u ,i}\) 为路径大小为 \(dis_u + i\) 的方案数，假设当前没有零边。

对于边 \((u ,v ,w)\)，考虑对于所有 \(v\) 对 \(u\) 的贡献，此时必有 \((v ,u) \in E\)（我也不到为啥不 \(u ,v\) 啊），设要更新的状态为 \(f_{u ,s}\)，转移状态为 \(f_{v ,x}\)，通过 \((v ,u ,w)\) 到点 \(u\) 路径权值为 \(dis_v + x + w\)，则 \(dis_v + x + w = dis_u + s ,x = dis_u + s - dis_v - w\)。

因此

\[f_{u ,s} = \sum_{(v ,u) \in E} f_{v ,dis_u + s - dis_v - w} \]

建立反图，从 \(n\) 开始，改写条件为 \((u ,v) \in E\)，记忆化即可（个人感觉有点绕理解了好久 QWQ）。

注意到这个转移如果绕环后面的必然变化啊，不会有后效性。

考虑零边，此时如果 \(1 \sim n\) 有 \(\le dis_n + k\) 的路径经过零环，则无穷解，转移时必然会转移回自己，用 \(vis_{u ,s}\) 表示节点 \(u\) 是否正在转移，如果遍历到则无穷解。

注意这里判无穷解时不要 \(f_{1 ,0} = 1\)，否则若 \((1 ,x)\) 为零边则无法判无穷解（样例二）。

CF888G

• 死因：真不会啊。

考虑合并两个连通块，代价为连通块之间点权的最小值，可以一半插 trie 另一半查询得到。

直接 Kruskal 是不行的，考虑 trie 树上分治？！每次合并左、右儿子，问题转化为求左、右儿子包含哪些 \(a\) 中元素。

trie 树第 \(dep\) 层（根为 \(1\)，深度从上到下由 \(30\) 递减）分为左儿子【\(dep + 1 \sim 30\) 位由祖先决定，\(dep\) 位为 \(0\)】和右儿子【更高位同理，但 \(dep\) 位为 \(1\)】，考虑将 \(a\) 排序，那么符合条件的一定是连续的一段，预处理插入 trie 时可以预处理。

另外这题不用启发式合并（插小的查大的），因为深度最多 \(30\)。

CF891C

P9140