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
跑树的直径即可。
复盘:比较经典,比赛应该不会出这种板子,这题可以巩固一下对桥的理解。