做题记录 25.9.17

· · 个人记录

QOJ #10740. Colorful Graph

显然答案的下界为 \sum \lceil\frac{d_i}2\rceil，每次取一个环染上一个颜色即可取到

显然奇度数点数量为偶数，将它们两两配对，分别连边，显然得到的图每个连通块都有欧拉回路，求出欧拉回路后拆成若干环处理即可

时间复杂度 O(\sum(n+m))

代码

参考

\purple\odot P7737 [NOI2021] 庆典

先缩点，对得到的 \text{DAG} 拓扑排序，每个点保留拓扑序最大的入边，得到一棵叶向树

对于一组询问，求出叶向树上的虚树，然后加上两条额外边，得到一个大小 O(k) 的图，点有点权表示原图上对应 \text{SCC} 的大小，边有边权表示缩点后图上对应路径（不含端点）的点权和

询问的答案就是该图上能从 s 出发到达且能到达 t 的点和边的权值和

时间复杂度 O(n+m+qk\log n)

代码

参考