Loading... ### 张浩威老师的图论 <!--more--> #### 存图 * 过（太菜了） #### 概念 * 过（awsl） * 如果一个图中节点两两相连，那么称这是一个团。 * * * #### 拓扑排序（DAG一定存在） * 例如：  * $v1,v2,v5,v4,v3,v7,v6$为该图的一个拓扑序。 * 我们每次寻找入度为$0$的点加入序列中。 * 并将当前点连接的所有边均删除，更新其它点的度数。 * 由于每条边至多被删除一次。 * 因此这个时间复杂度是$O(|E|)$的。 ```cpp cin>>n>>m; vector <int> a[]; while (m--) { cin>>A>>B; a[A].push_back(B); du[B] ++; } for (int i=1; i<=n; i++) if (du[i] == 0) { ans[++r]=i; } l=0; while (l!=r) { now = ans[++l]; cout<<now<<' '; for (int i=0; i<a[now].size(); a++) { du[a[now][i]] --; if (du[a[now][i]] == 0) ans[++r]=a[now][i]; } } ``` #### 拓扑排序计数 * 状压DP？ #### 求“割点” * 给定一张n个点m条边的拓扑图（保证1号点能走到n号点），求存在多少点，将其删去后1号点走不到n号点。 * $n,m\\leq 100000$ * 这个题和图论没啥关系…… * 令$S\[i\]$表示从1号点走到i号点的方案总数，令$T\[i\]$表示从n号点反向走到i号点的方案总数。（这个可以用动态规划求出） * 对于一个点i，若$S\[i\]*T\[i\]=S\[n\]$，则它是割点。 * * * ### 最短路 #### Dijkstra * 令dis\[i\]表示当前u到i的最短路是多少。 1. 将dis\[u\]=0,dis\[i\]=inf(i!=u)。 2. 寻找最小的dis\[x\]且x曾经没被找到过。 3. 若x=v，输出答案并退出。 4. 枚举x的所有边，用dis\[x\]去更新其余dis\[\]，回到步骤2。 * 时间复杂度为$O(n^2)$。 * 使用范围：不存在负权边。   * * * #### SPFA * 令dis\[i\]表示当前u到i的最短路是多少。 1. 将$dis\[u\]=0,dis\[i\]=inf(i!=u)$，并将u加入队列中。 2. 设当前队首为$x$，枚举$x$。 3. 枚举x的所有边，用$dis\[x\]$去更新其余$dis\[\]$，若$dis\[i\]$此时被更新且$i$当前不在队列中，将其加入队列。 4. 将$x$弹出队列，若此时队列为空，结束，否则返回步骤2。 复杂度$O(nm)$  * 判断负环：如果有一个点进入队列超过$n-1$次，就有负权环。 * * * ### 差分约束 * 设有$n$个变量和$m$个约束条件。 * 第i个约数条件形如$x\[ai\]-x\[bi\] \\leq ci$，我们称之为差分约数系统。 * 求解一组解使得这$n$个变量满足所有约束条件即为差分约束系统。 #### 解决 * 对于一个ai - bi <= ci的限制 * 我们抽象成bi -> ai 有一条长为ci的边。 * 在跑最短路时，就保证了ai至多为bi+ci。 * 具体实现时可以再增加一个虚拟点来作为源点跑最短路。  * * * ### 并查集 * 过 * * * ### 二分图 * 定义：如果一个无向图$G$中$V$能分成两个点集$A$与$B$，且位于$A$中的顶点互相之间没有边，位于$B$中的顶点互相之间没有边，则称这个图为二分图。 * 性质： 1. 这个图中不存在奇环，反之如果不存在奇环，那它一定是一个二分图。 * 判断二分图：用并查集，先将每个点分成两个点，比如点$A$分成$A$和$A^'$，然后每遇到一条边，都把$A$和$B^'$,$B$和$A^'$用并查集合并，然后当发现$A$和$A^'$被合并时，说明这不是二分图。 代码如下： ```cpp for (i=1; i<=n; i++) p[i][0]=++cnt,p[i][1]=++cnt; for (i=1; i<=cnt; i++) f[i]=i; while (m--) { cin>>A>>B; f[get(p[A][0])]=get(p[B][1]); f[get(p[A][1])]=get(p[B][0]); if (get(p[A][0]) == get(p[A][1]) || get(p[B][0]) == get(p[B][1])) return false; } ``` #### 匈牙利算法（二分图最大匹配） ```cpp bool work(int x) // 编号为x的男生是否能匹配女生 { for (int i=1; i<=m; i++) if (a[x][i]) //如果有边相连 { if (!t[i]) //该女生还未匹配 { t[i] = x; return true; } if (!v[i]) { v[i]=true; if (work(t[i])) { t[i] = x; return true; } } } return false; } for (i=1; i<=m; i++) t[i]=0; // t[i] 编号为i的女生连接的男生编号 for (i=1; i<=n; i++) { for (j=1; j<=m; j++) v[j]=false; // v[j] 编号为j的女生对应的男生是否已经谦让过了 if (work(i)) ans++; } ``` * * * ### 搜索树 * 对一个图从某一点开始进行深度优先搜索。 * 搜索到的边构成的树称为搜索树。 * 在这棵树上的边称为树边，其余边称为非树边。 * 性质：对图求搜索树时，非树边连接的两个端点在搜索树中一定是其中一个点是另一个点的祖先。 * * * ### 强连通分量 * 求无向图的所有强连通分量 * 求联通块即可。 * 求有向图的所有强连通分量 * Tarjan! #### Tarjan  存在3个极大强连通分量，1234，5，6。 * 我们定义$DFN\[x\]$为搜索到x时的时间戳（即搜索到的时间）。$LOW\[x\]$为搜索树中x以及它的子孙可以访问到的最早祖先的时间戳。有$LOW\[x\]=min(DFN\[x\],DFN\[j\],LOW\[k\])$，其中存在边$(x,j)，(x,k)$，$j$为$x$的祖先，$k$为$x$的子孙。 * 令v\[i\]表示i是否已被搜索过以及是否找到了极大强连通分量。若i已经找到了极大强连通分量或者还未被搜索过，则$v\[i\]=0$，否则$v\[i\]=1$。 1. 如果出点是自己的祖先，则拿祖先的DFN值更新。 2. 如果出点不是自己的祖先，且出点的low值小于自己的DFN值，则可以用这个值更新自己的$low$值。 3. 直到$low=DFN$ 找到了一个极大强连通分量。 ```cpp void dfs(int x) { Time++; DFN[x] = Time; LOW[x] = Time; v[x]=1; // v为1的就表示x的祖先 st[++r] = x; //当前搜索树中未找到极大强联通分量的点的编号 int R=r; // R表示x在st中的位置 for (int i=0; i<a[x].size(); i++) { if (!DFN[a[x][i]]) dfs(a[x][i]); if (v[a[x][i]]) LOW[x] = min(LOW[x],DFN[a[x][i]]); if (!v[a[x][i]] && !g[a[x][i]]) LOW[x] = min(LOW[x],LOW[a[x][i]]); } if (LOW[x] == DFN[x]) //如果LOW[x] == DFN[x] 时 R~r一定构成极大强联通分量 { num ++; // 强联通分量的编号 for (int i=R; i<=r; i++) { g[st[i]] = 1; group[st[i]] = num; // group[i] i这个节点所在的编号 } r = R-1; } v[x]=0; } for (int i=1; i<=n; i++) if (!DFN[i]) dfs(i); } } ``` #### 无向图的割点和桥 * 我们称一个点$u$为这个图的割点，当且仅当删去这个点以及与该点连接的所有边后，这个图不连通。 * 我们称一条边$(u,v)$为这个图的割边，当且仅当删去这条边后这个图不连通。 * * * ### 倍增问题 * 给定n个数，有Q次询问，每次询问一段区间的最小值。 #### RMQ问题 * $f\[i\]\[j\]$表示从$i$开始，长度为$2^i-1$的序列的最小值。 * 我们考虑记录$a\[x\]~a\[x+2^k-1\]$的最小值，令其为$f\[x\]\[k\]$。这可以在nlgn的时间内求出。 * 对于每次询问$L~R$，令$k=log\[R-L+1\]$。有$ans=min(f\[L\]\[k\],f\[R-2^k+1\]\[k\])$。(即进行$O(1)$询问) ```cpp f[x][0] = a[x] f[x][i] x~x+2^i-1 f[x][i-1] x~x+2^(i-1)-1 f[x+2^(i-1)][i-1] x f[x][i] = min(f[x][i-1],f[x+2^(i-1)][i-1]) n i log(n)/log(2) for (i=1; i<=n; i++) LG[i]=int(log(i)/log(2)); // log(i) lglgi for (i=1; i<=LG[n]; i++) for (x=1; x<=n-(1<<i)+1; x++) f[x][i] = min(f[x][i-1],f[x+2^(i-1)][i-1]) ``` ### 求LCA * 先让两个点到同一深度，然后一起向上跳，当跳到的点相同时，就找见了LCA。 #### 倍增法 * 为了简化问题，我们假设$x,y$在同一高度。 * 令$f\[i\]\[j\]$表示i向上跳$2^j$步的父亲是啥。 * 将k从$logn$枚举到$0$，若$f\[x\]\[k\]$与$f\[y\]\[k\]$不同，则将$x$跳至$f\[x\]\[k\]$，将$y$跳至$f\[y\]\[k\]$。 * 最后若$x=y$，则$LCA=x$，否则$LCA=f\[x\]\[0\]$。 f[x][i] 表示从x出发向上跳2^i步能到达的点的编号 g[x][i] 表示x向上跳2^i步经过的路径中最长边是多少 ```cpp f[x][0] = fa[x]; g[x][0] = x和fa[x]的边的长度 for (i=1; i<=LG[n]; i++) for (j=1; j<=n; j++) f[j][i] = f[f[j][i-1]][i-1], g[j][i] = max(g[j][i-1],g[f[j][i-1]][i-1]); ``` 求出了以任意点为起点，向上跳2的幂次方步能跳到哪里 ```cpp cin>>x>>y; //dep表示深度 if (dep[x]>dep[y]) swap(x,y); // dep[x] <= dep[y] 因为LCA(x,y) == LCA(y,x) //y向上跳dep[y] - dep[x] 次 int leng=dep[y]-dep[x]; //tot = 0 while (leng) {idx = leng%2; if (idx == 1) y = f[y][tot]; tot+=1; leng/=2;} for (i=LG[n]; i>=0; i--) if (leng>=(1<<i)) leng-=(1<<i), MAX=max(MAX,g[y][i]),y=f[y][i]; if (x==y) {cout<<MAX; return 0;} for (i=LG[n]; i>=0; i--) if (f[x][i] != f[y][i]) //LCA(x,y) == LCA(f[x][i],f[y][i]) MAX=max(MAX,max(g[x][i],g[i])), x = f[x][i], y = f[y][i]; MAX=max(MAX,max(g[x][0],g[y][0])) cout<<MAX; ``` #### 链上最大值问题 * 给定一棵树，每次询问两个点x,y，求这两个点的路径上最长的边是多少。 ##### 解法： * 同样的令f\[i\]\[j\]表示i向上跳2^j能跳到哪儿。 * 也令g\[i\]\[j\]表示i向上跳2^j的过程中遇到的最长的边是多少。 * 现在我们先求出两个点x,y的LCA。 * 用倍增的方法求出x到LCA的最长边，y到LCA的最长边就可以了。 #### 链上和问题 * 给定一棵树，每次询问两个点x,y，求这条路径上边权和是多少。 #### 链上异或和 * 给定一棵树，每次询问两个点x,y，求这条路径上边权异或和是多少。 Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏