2024.2.6+2024.2.7上午

· · 个人记录

图论

坑：同余最短路

存图

vector,链式前向星（邻接链表）

并查集

启发式合并，路径压缩

带权并查集

种类并查集（扩展域并查集）

食物链

把一个点扩为x,x+n,x+2\times n三个点表示三个类群，然后判断

Parity Game

转化为前缀和s_y-s_x = 奇/偶

奇偶性相同的是一个集合，不同的是一个集合

然后连边，判冲突

也可用带权并查集

奇偶性相同的连0 边，不同的连1 边

序列并查集

P2391 白雪皑皑

用并查集维护 [连续攻击游戏](https://www.luogu.com.cn/problem/P1640) 将两个属性值连无向边 如果有环，就都能满足 如果是树，除根节点，都能满足 那就选最大的为根 求联通块的 $mex

（本题也可用二分图匹配）

最小生成树

Kruscal

Prim

P1396 营救

可二分

将<=n 的边加入图，看s,t是否联通

但是最小生成树显然更优

从小到大加入边，看是否联通

SVEMIR

一眼最小生成树

但是两两连边的话显然要炸

显然要去除冗边

分别按x,y,z排序

每个点向前后的点连边

跨过其他点连的边显然没用（跟他连边的代价都够把其间的点都联通了）

然后排三次序，跑最小生成树

（重边也没关系，因为最小生成树每次取权值最小的）

思维题

Kuglarz

转化为得知s_i (前缀和)的奇偶性

$s_0 =0

目的转化为求s_0,s_1,s_2......s_n 在同一连通块内的最小代价

于是将 s_{i-1} 与 s_j 连边，代价为 c_{i,j}

跑最小生成树

严格次小生成树

结论：严格次小生成树一定是拿非树边换树边

枚举所有非树边，尝试替换环上的边

（记录最大值和次大值，如果等于最大值，那么替换次大值，否则替换最大值）（非树边一定大于等于树边）

最短路

bfs

dijistra

spfa

floyd

Switch the Lamp On

原来的边权为0，转之后的边权为1,跑最短路

(因为每次的坐标x+1，y+1或x+1,y-1...,因此坐标之和奇偶性不变，因此一个格子不会既有左上到右下，又有左下到右上)

小优化：

因为是0/1最短路，跑bfs即可，复杂度O(n+m)

拓展：

边权为[0,k](k较小）

开k 个桶，把操作后的扔进相应桶里，从小到大枚举桶，时间复杂度（n+m），空间（nk+m）

通往奥格瑞玛的道路

二分，判最短路

P1144 最短路计数

P1119 灾后重建

冻结

分层图板子

Sightseeing Cows G

看到除法，二分 or 斜率优化

显然二分

如果二分出来的mid为 k，则问题就转化为是否存在一个\sum F_i/\sum T_i \ge k

\sum (F_i-k\times T_i)\ge0

然后 spfa 判环

骑士游戏

设 f_i 表示彻底消灭 i 的最小代价

f_i=min(k_i,s_i+f_j)

类比 dijistra

同余最短路

墨墨的等式

同余方程\to 最短路

$f_0=0 f_t \to (f_t+a_i)mod a_1$ 边权$a_i

跑最短路

f_t=min(f_{t-a_i}moda_1+a_i)

差分约束

a\to b$,边权为 $w$ 表示$b-a\le w

Layout G

差分约束板子

P5590 赛车游戏

差分约束妙用

1\le dis_b-dis_a\le9 dis_a-dis_b \le -1 dis_b-dis_a\le9

跑差分约束

拓扑排序

Andrew and Taxi

一眼二分

对> mid 的边拓扑

对于\le mid 的边

肯定是从小拓扑序的点指向大拓扑序的点

然后判断方向是否改变，判断是否可行，统计答案

菜肴制作

首先不是字典序最小

怎么办？

保证小的尽量在前面，即保证大的尽量在后面

把较小的放在后面，不如直接把最大的放在后面

我们可以建反图

跑一遍字典序最大的拓扑序，倒序输出，即为答案

基环树

Session in BSU

同前面的某一道题

城市环路

遍历切掉环上的一条边,跑最大独立集

(或随机选环上的一个点,强制选或不选,跑dp)

Island

转化题意,即求基环树(森林)上的直径

不经过环,直接dfs

经过环,求两段的最大值

Tarjan

BLO-Blockade

魔改割点

稳定婚姻

将夫妻和情人关系区分开连，一个男向女，一个女向男,跑tarjan

矿场搭建

二分图

假期的宿舍

板子

攻击装置

对能攻击到的染与自己不同的颜色，跑最大独立集

矩阵游戏

将每行看作点，每列看做点，一个黑格子就让行和列连边，跑最大匹配是否为 n

网络流

ek

dinic

重点在建图

番外

“奇技淫巧”

“精妙建图”