2023.8.9 做题记录
CF20C
题意：输出 \(1\sim n\) 的最短路路径。
分析：直接裸 bfs 记录松弛操作的上一个点即可。
复盘：不需要复盘。
CF840B
题意：给出若干条边，对于每个点给出 \(d_i=0/1/-1\)，若 \(d_i=1\) 则表示该点度数为奇数，若 \(d_i=0\) 则表示该点度数为偶数，若 \(d_i=-1\) 则表示该点度数无限制，请你在给出的边中选出几条边，使由这些边构成的图一定联通。
分析：考虑到每次加一条边会使得总度数增加 \(2\)，因此，图的总度数一定是偶数，因此若总度数为奇数且不含 \(-1\)（\(-1\) 可以随时调整总度数）则无解。
现考虑有解的情况，可以对原图构造一个生成树，在生成树上由下到上，根据子节点的现有度数决定是否与他的父节点连边，对于不是根节点的 \(-1\) 节点当偶数节点考虑。
考虑这样构造的正确性：
- 若 \(d_{root}=-1\)，显然可行。
- 若 \(d_{root}\neq -1\)，由于 \(root\) 的所有子树一定符合条件，因此目前总度数一定是偶数，所以若 \(root\) 还要向上连边，那么肯定总度数是奇数，本来就无解。
复盘：明天补。
CF1000E
题意：给出 \(n\) 个点，\(m\) 条边的无向图，保证图联通。求图上经过最多桥的路径。
分析：比较板，用 tarjan 求出无向图的所有桥，然后将边双的点缩成一个点，这时候图一定是一棵树，两次 dfs 跑树的直径即可。
复盘：比较经典，比赛应该不会出这种板子，这题可以巩固一下对桥的理解。