做题记录 25.9.15

szt100309 · 2025-09-15 13:03:26 · 个人记录

\blue\odot P3225 [HNOI2012] 矿场搭建

求出割点，枚举删去割点后的连通块，求出该连通块相邻的割点数量，设为 c，设连通块内点数为 s

若 c=0，表示原图中该连通块为整个点双，若 s=1（数据中没有这种情况）则答案增加 1 且方案数不变，否则令答案增加 2，方案数乘以 \binom s2

若 c=1，则答案增加 1 且方案数乘以 s

若 c\ge 2 则忽略

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

代码

参考

边双缩点，则一次询问的答案为边双树上的距离，树剖即可

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

代码

一张图为半连通的当且仅当 \text{SCC} 缩点后为一条链

因此求出 \text{SCC} 后在 \text{DAG} 上 \text{dp} 即可，时间复杂度 O(n+m)

代码

先跑一次最大流，用残量网络建立有向图

一条边 u\to v 为可行边当且仅当 u\to v 满流且残量网络上不存在 u\to v 的边，即残量网络上 u 和 v 不属于同一 \text{SCC}

证明：若 u\to v 不满流，显然割开 u\to v 不优，若 u\to v 满流，则残量网络上必然存在 v\to u，若残量网络上存在 u\to v 的路径，显然割开 u\to v 不优，此时残量网络上存在包含 u,v 的环，即 u,v 在同一 \text{SCC} 中

一条可行边为必经边当且仅当在必经边的基础上，s 可以到 u 且 v 可以到 t，即 s 和 u 属于同一 \text{SCC} 且 v 和 t 属于同一 \text{SCC}

总时间复杂度 O(m\sqrt n)

代码

参考

逆序考虑，转化为一个位置第一次被填上以后就无法修改

显然 (u,2,v,2) 型的放到最前面，(u,1,v,1) 型的放到最后面，不妨设剩下的都是 (u,1,v,2) 型，这样一组记为 (u,v)，显然 (u,v) 放到 (v,w) 前更优

建立图，对于一组 (u,v) 连边 u\to v，转化为每次染一个点，或选择一个已经染色的点和它的一条出边，将到达的点染色，最小化前一种操作数量

显然染一个点的操作只会发生在入度为 0 的 \text{SCC} 中，且每个这样的 \text{SCC} 中至多选择一个即可

特别地，若一个入度为 0 的 \text{SCC} 中存在 (u,2,v,2) 型（u,v 之一在当前 \text{SCC} 中），则无需单独染色

显然这样最优

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

代码

参考