杂项概念

距离

曼哈顿距离（Manhattan Distance）：

它表示两点在一个标准的笛卡尔坐标系上沿着网格状的路径之间的距离。

计算公式：$d_{\text{Manhattan}}(P, Q) = \sum_{i=1}^{n} |p_i - q_i|$ 其中， $P = (p_1, p_2, \ldots, p_n)$ 和 $Q = (q_1, q_2, \ldots, q_n)$ 是两个点的坐标。

欧几里得距离（Euclidean Distance）：

它表示两点之间的直线距离，可以看作是空间中两点之间的实际距离。

计算公式：$d_{\text{Euclidean}}(P, Q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$

特殊图

竞赛图：简单来说，竞赛图就是将完全无向图的无向边给定了方向。

网络流

最短路

算法

SPFA

优化

SLF 优化

即 Small Label First

更新距离后，发现队头距离大于队尾距离就 swap 对头和队尾

不需要使用 deque 可以大幅降低构造图上跑的时间但是仍可以被专门针对卡掉随机图无明显优化

影响判负环

Floyd

求最小环

 for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i != j && i != k && k != j) 
                ans = std::min(ans, d[i][j] + g[j][k] + g[k][i]);
                d[i][j] = std::min(d[i][k] + d[k][j], d[i][j]);
            }
        }
    }

Johnson

跑 spfa 求势能 ( $d[v]\leq d[u]+w \ 则有\ 0\leq d[u]-d[v]+w$ )

改边权

跑 n 次 dij，还原边权

DAG 上的Tricks

$u\in V$ 要求以 u 结尾的最长路，直接拓扑排序即可如果要求以 u 开始的最长路，沿着反边再跑一遍即可

建图技巧

拆点或加点

多步代价通过拆出多个点解决

“出口点”+“入口点”形式能强制增加点权

新建点或链实现多对多转成多对一

多源问题

多源单汇：将图反过来变成单源多汇

多个源之间是竞争关系：转化为有初值的问题

都无法解决时，只能对每个源都跑一次最短路或使用全源最短路算法

带有初值：dist 赋初值，或建超级源点

决策序优化降维

优化一（自带部分拓扑序）：能分出若干子图，子图内无拓扑序，子图间有拓扑序特征：子图间有拓扑序，子图内是最短路问题解法：选择子图内最短路算法和普通最短路问题逻辑相同，常常用到有初值的最短路有时图有显式的层次，有时需要自己分析出部分拓扑序

优化二（求最短路后造出部分拓扑序）：求两两最短路后，原图可能出现拓扑序特征：图有重复，走完最短路能推进进程等解法：两两最短路可能用 Floyd，也可能跑多次单源最短路，有时需挑出关键点进一步优化本质等价于预处理“有部分拓扑序的图”中无拓扑序的子图

差分约束系统

特征

差分约束系统一定是一组形式如下的不等式（常量一定大）

$x_1-x_2\leq w_A$ $x_2-x_3\leq w_B$ $...$

建模

$a-b\leq w$ 有两种变形方式

$a\leq b+w$ 可求最大值

$b\geq a-w$ 可求最小值求原图边反向+边权取相反数+求最长路等价于求原图边反向+边权+最短路后将结果取相反数

初始值设置：根据题意设置超级源点即可

连通性问题

算法

SCC

void Dfs(int u)
{
    if(dfn[u]) return ;
    instk[u] = 1, stk[++top] = u, dfn[u] = low[u] = ++idx;
    for (int v : e[u])
    {
        if (!dfn[v]) Dfs(v), low[u] = std::min(low[u], low[v]);
        else if (instk[v]) low[u] = std::min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        cnt++;
        do instk[stk[top]] = 0, siz[cnt]++, where[stk[top]] = cnt;
        while (stk[top--] != u);
    }
}

割点

void Dfs(int u, int father)
{
    int son = 0;
    dfn[u] = low[u] = ++idx;
    for (int v : e[u])
    {
        if (!dfn[v])
        {
            Dfs(v, u), low[u] = std::min(low[u], low[v]), son++;
            if ((father == u && son >= 2) || (father != u && low[v] >= dfn[u]))
                cutcnt += (iscut[u] ? 0 : 1), iscut[u] = 1;
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
}

割边

void Dfs(int u, int father)
{
    if (dfn[u]) return;
    dfn[u] = low[u] = ++idx;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (father == v) continue;
        if (!dfn[v])
        {
            Dfs(v, u), low[u] = std::min(low[u], low[v]);
            if (low[v] > dfn[u]) b[++cnt] = {std::min(u, v), std::max(v, u)};
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
}

VDCC

void Dfs(int u, int father)
{
    if (father == u && !e[u].size()) vdcc[++cnt].push_back(u);
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    for (int v : e[u])
    {
        if (v == father || v == u) continue;
        if (!dfn[v])
        {
            Dfs(v, u);
            low[u] = std::min(low[u], low[v]);
            if (low[v] >= dfn[u])
            {
                cnt++;
                while (stk[top] != v) vdcc[cnt].push_back(stk[top--]);
                vdcc[cnt].push_back(v), top--;
                vdcc[cnt].push_back(u);
                //重点：必须保证只出栈v子树的点和割点本身
                //因为u可能有另一棵子树，这棵子树的点不会被割掉且还在栈里，
                //如果一直出栈到u就会把这棵子树的点也弹掉，寄
                //eg：树边 13 35 52 27 24 46 返祖 63
            }
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
}

EDCC

void Dfs(int u, int father)
{
    if (dfn[u]) return ;
    instk[u] = 1, stk[++top] = u, low[u] = dfn[u] = ++idx;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if ((i ^ 1 )== father) continue;
        if (!dfn[v]) Dfs(v, i), low[u] = std::min(low[u], low[v]);
        else low[u] = std::min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        cnt++;
        do edcc[cnt].push_back(stk[top]), instk[stk[top]] = 0;
        while (stk[top--] != u);    
    }
}

构造圆方树

求 VDCC

每个 VDCC 对应一个方点，VDCC 内的每一个点向方点连边

对于孤立点，根据题目讨论

![[block-forest2.svg]]

常用结论

最少加边得到强连通图

𝑛（≤ 1e5）个点 𝑚（≤ 2e5）条边的有向图问最少添加多少条边，使得任何一个点到任何一个点都有路径

sol:

缩点

答案为新图入度总数与出入总数的较大值或新图只有一个强连通分量，答案为 0

构造/证明：

设有 𝑝 个弱连通分量，每个弱连通分量随便选一个没有入度的 SCC 𝑖1, 𝑖2, … , 𝑖𝑝 和一个没有出度的 SCC 𝑜1, 𝑜2, … , 𝑜𝑝，其中 𝑖𝑘 和 𝑜𝑘 在同一个弱连通分量中

连边 𝑜𝑘, 𝑖𝑘 mod 𝑝+1 ，构成一个环，连边 𝑝 条

接下来每次任取一个无出边的 SCC 和一个无入边的 SCC 连边

其他图论

二分图

概念

二分图是无向图

将二分图上的点划分为两个集合，可以保证存在一种方案使得与任意节点相邻的所有节点都与这个节点不在同一个集合内

判定

染色

无向图 G 无奇环 <-> 无向图 G 是二分图

可以使用扩展域并查集或 DFS 染色

int Dfs(int u, int color)
{
    int res = 1;
    c[u] = color;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (!c[v]) res &= Dfs(v, 3 - color);
        else if (c[v] == c[u]) res = 0;
    }
    return res;
}

匹配

$|最大匹配|=|最小点覆盖|=a$

$|最大独立集|=|最小边覆盖|=b$

$a+b=|V|$

如果不划分二分图，则求出的结果为正确答案的二倍

DAG 链覆盖

DAG 最小不可重链覆盖

拆点

如果图 G 中存在有向边 i⇒j，则在二分图中引入边 i⇒′j

设二分图的最大匹配数为 m，则结果就是 n−m

对于链覆盖中的每条链，除了最后一个“结尾结点”之外都有唯一的后继与它对应（即匹配结点），因此匹配数就是非结尾结点的个数。

当匹配数达到最大时，非结尾结点的个数也将达到最大。此时，结尾结点的个数最少，即链条数最少

DAG最小可重链覆盖

Floyd 求原图的传递闭包，接着求闭包偏序集的最小不可重链覆盖

欧拉路径

存在判断

无向图欧拉回路：所有点度都是偶数

无向图欧拉路径：有且仅有两个点度为奇数

有向图欧拉回路：所有点的入度等于出度

有向图欧拉路径：有且仅有一个点入度比出度多一有且仅有一个点出度比入度多一

算法

核心：把路径上的节点替换为环如果是欧拉回路，那么Dfs的时候就可以直接输出如果是欧拉路径，那么Dfs直接输出就可能出错如1->2 2->1 1>-3 入1 显然可能直接走3了寄采用后序遍历，如果走到环，肯定会回到这个点，等u遍历完才能入栈，所以链的部分一定是最先开始回溯的，也就是最先入栈的，推广到整张图，入栈顺序其实是找的欧拉路的逆序所以需要用栈，其实就是为了倒着输出找到的路径至于字典序最小，每个点给出边排序即可

void Dfs(int u)
{
    for (int &i = cur[u]; i < (int)e[u].size();) Dfs(e[u][i++]); // 巧妙至极
    stk.push(u);
}
void Euler_path()
{
    for (int i = 1; i <= n; i++)
    {
        std::sort(e[i].begin(), e[i].end());
        if (std::abs(rin[i] - rout[i]) > 1) cout << "No", exit(0);
        if (rin[i] == rout[i] - 1)
        {
            if (!st) st = i;
            else cout << "No", exit(0);
        }
    }
    Dfs(st ? st : 1);
    while (!stk.empty())
    {
        cout << stk.top() << " ";
        stk.pop();
    }
}

生成树

最小生成树

非严格次小生成树

先求最小生成树，枚举每一条非树边替换其对应的树上简单路径上的最大边即可

严格次小生成树

同上，发现非树边与树上路径上的最大边边权相同时，替换路径上的次大边即可

维护次大边的方法:

[[P4180【BJWC2010】严格次小生成树]]

fa[u][k] = fa[fa[u][k - 1]][k - 1];
mx[u][k] = std::max(mx[fa[u][k - 1]][k - 1], mx[u][k - 1]);
se[u][k] = std::max(se[fa[u][k - 1]][k - 1], se[u][k - 1]);
if (mx[u][k - 1] > mx[fa[u][k - 1]][k - 1]) 
se[u][k] = std::max(se[u][k], mx[fa[fa[u][k - 1]][k - 1]]);
if (mx[u][k - 1] < mx[fa[u][k - 1]][k - 1]) 
se[u][k] = std::max(se[u][k], mx[fa[u][k - 1]]);

浅谈图论

杂项概念

距离

特殊图

网络流

最短路

算法

SPFA

优化

SLF 优化

Floyd

求最小环

Johnson

DAG 上的Tricks

建图技巧

拆点或加点

多源问题

决策序优化降维

差分约束系统

特征

建模

连通性问题

算法

SCC

割点

割边

VDCC

EDCC

构造圆方树

常用结论

最少加边得到强连通图

其他图论

二分图

概念

判定

染色

匹配

DAG 链覆盖

DAG 最小不可重链覆盖

DAG最小可重链覆盖

欧拉路径

存在判断

算法

生成树

最小生成树

非严格次小生成树

严格次小生成树

状态

开发

支持

还没有账户？

登录