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\) 即可