OI易错点-图论

一、图论基础

【易错点】

1. ❗️新建虚拟结点 $\boldsymbol{0}$ ，会向至多 $n$ 个结点连边，空间要开 $\boldsymbol{2}$ 倍 ❗️
2. 无向图+链式前向星， $\boldsymbol{2}$ 倍空间
3. 多组数据不要忘了清空 pos
4. 邻接矩阵处理重边 down(g[u][v], w) （无向图别忘了 g[v][u] ）
5. ❗️树的欧拉序长度为 $3n$ ，因此线段树要开 $12n$❗️

【算法相关】

1. 自环要写 if(u==v)continue; 处理！
2. ❗️树上dp题获取子节点个数，不可以直接用 vec[u].size() ，因为可能有重边❗️
3. 二叉树的树高并不是固定 $\mathcal{O}(\log n)$ 的，链也满足二叉树的定义，概念不要混淆了。

二、最短路算法

【易错点】

1. $\text{Dijkstra}$ 不要忘记把起点入队

2. $\text{Floyd}$ 相关问题注意 $\text{INF}$ 值的设置不能过大

   如 0x3f3f3f3f3f3f3f3f 在 f[i][j]+g[i][k]+g[k][j] 时很可能会溢出

【算法相关】

1. $\text{SPFA}$ 已死，能不用就不用

【相关问题1】无向图最小环问题

【算法相关】

1. 在Floyd算法枚举 $k_i$ 的时候，已经得到了前 $k-1$ 个点的最短路径

   这 $k-1$ 个点不包括点 $k$ ，并且他们的最短路径中也不包括 $k$ 点

【相关问题2】分层图（最短路）

【易错点】

1. ❗️无向图的 e[SIZE] 数组大小为❗️ $$M\times (K+1) \times 4$$

【算法相关】

1. 用 $\text{Dijkstra}$ 的时间复杂度 $O(nk\log mk)$

2. ❗️要注意 $k>(s \to t)$ 的情况，也就是路径的结点数比 $k$ 小时，需要加边❗️

   for(int i=1; i<=k; i++)
       addEdge((i-1)*n+t,i*n+t,0);

三、Tarjan算法 [连通性问题]

【算法相关】

1. ❗️无向图割点割边不能在函数内计算数量，会重复计算，即 hack: (1,2)(1,3)(1,4)❗️

   // 这里是一个正确的函数板子
   void Tarjan(int u,int f)
   {
       static int tim = 0; int C = 0;
       dfn[u] = low[u] = ++tim;
       for(int i=head[u]; i; i=e[i].next)
       {
           int v = e[i].v;
           if(!dfn[v])
           {
               ++C; Tarjan(v,u); down(low[u], low[v]);
               if(f && dfn[u] <= low[v]) cut[u] = 1;
           }else if(v != f) down(low[u], dfn[v]);
       }
       if(!f && C>1) cut[u] = 1;
   }

2. 求强连通分量，在不连通的图要写

   for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);

四、树上差分

【算法相关】

1. 点权差分：在 $u$ 加上 $x$ ，在 $v$ 加上 $x$ ，在 $\mathrm{lca}(u,v)$ 减去 $2x$
2. 边权差分：在 $u$ 加上 $x$ ，在 $v$ 加上 $x$ ，在 $\mathrm{lca}(u,v)$ 减去 $x$ ，在 $\mathrm{fa}(\mathrm{lca}(u,v))$ 减去 $x$

五、线段树优化建图

【算法相关】

1. 注意要记录结点 $i$ 对应入树的叶子结点的编号，这两个是不一样的！

六、最小生成树

【算法相关】

1. 要注意图是否连通，如果不连通可能需要加虚点，同时注意边数变化

七、差分约束

【算法相关】

1. 差分约束建边，$x-y\le w$ ，则 $\boldsymbol{y \to x}$ ，因为 $d_y+w\ge d_x$

八、网络流

【算法相关】

1. 网络流反向边流量为 $\boldsymbol{0}$ addEdge(u,v,w);addEdge(v,u,0);
2. 二分图最大匹配数=最小点覆盖数 （König定理）

九、二分图最大权匹配

【算法相关】

1. 多组匹配要注意清空

   for(int i=1; i<=n; i++)
       px[i]=py[i]=lx[i]=ly[i]=pre[i]=0;

2. 初始化边权为 $\mathrm{-INF}$ ，且要保证左部点个数小于等于右部点个数

   如果是非完美匹配，就将虚边边权设为 $0$ 即可