省选初级图论

高级的图论知识会包含更多的内容。我们将二分图与网络流排除，这篇文章的内容会覆盖绝大多数简单常用的图论知识点与技巧。

热身

搞一些基础内容！

拆边拆点与点边转化

有些时候的问题比较复杂，我们可以选择将边或者是点进行拆分，来更加方便的处理。比如分层图最短路中，我们使用的就是"点拆点"，把一个点拆成多个点进行维护。当然，这也意味着分层图中的"特殊道路"不会很多，否则点会被拆成很多，复杂度无法承受。

有的时候点或者边不方便做，两者甚至可以相互转化。比如在处理树上边权时，我们就采取了把边权下放到点权的方式。

这种思想在网络流中还有更多应用，所以在这里只简单介绍几个例子。

点拆点 | [SCOI2009] 迷路

Portal.

一个有向图有 $n$ 个节点，从节点 $1$ 出发，必须恰好在 $t$ 时刻到达节点 $n$ 。求共有多少种不同的路径吗？答案对 $2009$ 取模。注意：不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。保证 $2 \leq n \leq 10$ ， $1 \leq t \leq 10^9$ 。

我们先考虑边权只有 01 怎么做。

设 $f(t,i,j)$ 表示 $i$ 到 $j$ 的长度为 $t$ 的路径数，显然 $t=1$ 时这个就是初始矩阵，转移也就是 $f(t,i,j)=\sum_{k=1}^{n}f(t-1,i,k)+f(1,k,j)$ 。当然这个转移也可以扩展到任意情况，不过与我们接下来讨论的内容没有关系。

这种时候可以发现 $f(t)=f(t-1)\times f(1)$ ，那么可以使用矩阵快速幂计算。然而当不全是 01 的时候无法使用矩阵快速幂！怎么办？发现 $w<10$ ，我们可以将一个点拆成九个点，像这样：

如果我们要连一个点到这个被拆好的点，那么根据距离连接即可。比如有一个点与它距离为 $3$ ，那么就需要连接到 $2$ 号点。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int MOD = 2009;

int m;

struct Matrix {
    int a[100][100];
    Matrix() { memset(a, 0, sizeof(a)); }
    Matrix operator * (const Matrix &a) const {
        Matrix res;
        for (int i = 1; i <= m; ++i)
            for (int k = 1; k <= m; ++k) {
                i64 r = this->a[i][k];
                for (int j = 1; j <= m; ++j)
                    res.a[i][j] = (res.a[i][j] + r * a.a[k][j]) % MOD;
            }
        return res;
    }
};

Matrix poww(Matrix a, int b) {
    Matrix res; for (int i = 1; i <= m; ++i) res.a[i][i] = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int n, t;

int main(void)
{
    scanf("%d%d", &n, &t);
    m = 9 * n;
    Matrix f;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 8; ++j)
            f.a[i + j * n][i + (j - 1) * n] = 1;
        for (int j = 1; j <= n; ++j) {
            int x;
            scanf("%1d", &x);
            if (x) f.a[i][j + (x - 1) * n] = 1;
        }
    }
    f = poww(f, t);
    printf("%d\n", f.a[1][n]);
    return 0;
}

边转点 | [SDOI2009] HH去散步

Portal.

给定一张不带权的无向图，不会立刻沿着刚刚走来的路走回，问有多少种从 $A$ 走到 $B$ ，距离为 $T$ 的走法？

感觉根上一题很相似，但是要求不能来回走！怎么办？考虑将一条无向边转换成两个点，然后这两个点之间不连边，剩下的能到达的边与这些点连边。

初始时连一条 $0\rightarrow a$ 的边，建立初始矩阵的时候枚举两条边 $i,j$ ，如果满足 $v[i]=u[j]$ ，而且不是反向边，那么 $i\rightarrow j$ 就可以用 $1$ 的时间去到达。答案也是枚举所有边，第一条边 $0\rightarrow a$ 到当前的边 $k\rightarrow b$ 的答案的和。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 45989;

int N;
struct Matrix {
    int a[125][125];
    Matrix() { memset(a, 0, sizeof(a)); }
    void build(void) { for (int i = 0; i < N; ++i) a[i][i] = 1; }
    Matrix operator * (const Matrix &b) const {
        for (int i = 0; i <= N; ++i)
            for (int k = 0; k <= N; ++k) {
                int r = a[i][k];
                for (int j = 0; j <= N; ++j)    
                    c.a[i][j] = (c.a[i][j] + r * b.a[k][j]) % MOD;
            }
        return c;
    }
};

Matrix poww(Matrix a, int b) {
    Matrix res; res.build();
    for (; b; b >>= 1, a = a * a) 
        if (b & 1) res = res * a;
    return res;
}

struct edge { int u, v; };
int n, m, t, a, b;
int u[125], v[125], cnt = 0;

int main(void)
{
    scanf("%d%d%d%d%d", &n, &m, &t, &a, &b); ++a; ++b;
    u[++cnt] = 0; v[cnt] = a;
    while (m--) {
        int x, y; scanf("%d%d", &x, &y); ++x; ++y;
        u[++cnt] = x; v[cnt] = y;
        u[++cnt] = y; v[cnt] = x;
    }
    Matrix f;
    N = cnt;
    for (int i = 1; i <= cnt; ++i)
        for (int j = 1; j <= cnt; ++j)
            if (i != j && i != (j ^ 1) && v[i] == u[j])
                f.a[i][j] = 1;
    f = poww(f, t);
    int ans = 0;
    for (int i = 1; i <= cnt; ++i)
        if (v[i] == b) ans = (ans + f.a[1][i]) % MOD;
    printf("%d\n", ans);
    return 0;
}

基础概念

一个点可以连接到图中的所有点，那么这个点是图的支配点。

对于一张图 $G=(V,E)$ ，若图 $G'=(V',E')$ 满足 $V'\subseteq V,E'\subseteq E$ ，则称 $G'$ 是 $G$ 的子图。

如果 $G'$ 满足 $\forall u,v\in V'$ ，只要 $(u,v)\in E$ ，均有 $(u,v)\in E'$ ，则称 $G'$ 是 $G$ 的导出子图。

如果 $G'$ 满足 $V'=V$ ，则称 $G'$ 是 $G$ 的生成子图/支撑子图。

对于一张无向图 $G=(V,E)$ ，如果每个顶点的度数都是一个固定的常数 $k$ ，则称 $G$ 为 $\bold{k-}$ 正则图。而无向图的某个生成子图 $G'$ 为 $k-$ 正则图，则称 $G'$ 为 $G$ 的一个 $\bold{k-}$ 因子。

一张无向简单图的补图的含义是原本有的边都没有，原本没有的边都有。

一张有向图的反图是所有边方向改变。

覆盖

对于无向图 $G=(V,E)$ ，若 $V'\subseteq V$ ，有任意一条边都有一个端点在 $V'$ 中，则 $V'$ 称为 $G$ 的点覆盖集。一个点集是点覆盖的充要条件是其补集是独立集。

如果 $E'\subseteq E$ ，任意一个点都至少连了一条 $E'$ 中的边，则称 $E'$ 是边覆盖集。

最大团问题

一个图的子点集 $V'$ 中任意两个不同的顶点都相邻，则称 $V'$ 是图 $G$ 的一个团。团对应的导出子图是完全图。说白了最大团就是最大完全子图。

求解一个图的最大团是 NPH 的。下面的暴力一般可以应对 $n\le 50$ 的数据：

int cnt[2005], group[2005], vis[2005], ans;                      
bool dfs(int pos, int num) {  
    for (int i = pos + 1; i <= n; i++) {
        if (cnt[i] + num <= ans) return false; // 不可能成为答案
        if (G[pos][i]) {  
            int j;
            for (j = 0; j < num; j++) if (!G[i][vis[j]]) break; // 检查 i 是否与所有点相邻
            if (j == num) {
                vis[num] = i;
                if (dfs(i, num + 1)) return true;
            }
        }
    }
    if (num > ans) {
        for (int i = 0; i < num; i++) group[i] = vis[i]; ans = num;
        return true;
    }
    return false;
}

main(void) {
    for (int i = n; i >= 1; --i) vis[0] = i, dfs(i, 1), cnt[i] = ans; // 以 i 为起点找最大团
}

补图的最大团就是原图的最大独立集。

最短路问题

常规的最短路可以考虑以下求解方式：

01 最短路，可以使用双端队列 bfs 解决；
单源最短路，考虑使用 SPFA 或 Dijkstra，某些题目的图不太能特殊构造，那么使用 SPFA 会很快；
多源最短路，使用 Floyd 或者 Johnson（并没有什么优势）解决。

最短路有一些应用。包括已经讲过的差分约束，这里再补充两个知识点。

斯坦纳树

费马点问题是一个经典的几何问题，而它给定的是三角形。如果给定 $n$ 个点，试求连接此 $n$ 个点，总长最短的直线段连接系统，并且并且任意两点都可以通过系统中的直线段组成的折线连接起来，此问题被称为斯坦纳树问题。给定 $n$ 个点时，最多有 $n-2$ 个复接点（斯坦纳点）。每一斯坦纳点要么有三条边通过（呈 $120\degree$ 的夹角），要么是两条边，这时它是一个已经给定的点。

最小斯坦纳树。

给定一个 $n$ 个点 $m$ 条边无向图 $G=(V,E)$ ，再给定包含 $k$ 个节点的点集 $S$ ，选出 $G$ 的连通子图 $G'=(V',E')$ ，要求：

$S \subseteq V'$ ，
$E'$ 中所有边的权值和最小。

你需要求出这个最小权值和， $n\le 100,m\le 500,k\le 10$ 。

并不是直接将 $S$ 连接起来就是最小的，可能需要借助剩下的 $n-k$ 个点。这种问题可以使用状压 DP 来解决：

设 $f(i,S)$ 表示以 $i$ 为根的一棵树，包含集合 $S$ 中所有点的最小边权值和。有转移： $f(i,S)\leftarrow\min\{f(i,T)+f(i,S-T)\},f(i,S)\leftarrow\min\{f(j,S)+w(i,j)\}$ 。前者可以使用子集 DP 实现，后者可以跑一个最短路（由于图很难特殊构造而且规模很小，所以实际上更建议 SPFA）。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

int n, m, k, f[1024][105];
vector<pair<int, int>> G[105];

priority_queue<pii, vector<pii>, greater<pii>> q;
bool vis[105];
void dijkstra(int s) {
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < n; ++i) if (f[s][i] != INF) q.emplace(f[s][i], i);
    while (!q.empty()) {
        pii tmp = q.top(); q.pop(); int u = tmp.second;
        if (vis[u]) continue; vis[u] = true;
        for (auto [v, w] : G[u])
            if (f[s][v] > f[s][u] + w) q.emplace(f[s][v] = f[s][u] + w, v);
    }
}

int main(void) {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w); --u; --v; 
        G[u].emplace_back(v, w); G[v].emplace_back(u, w);
    }
    memset(f, 0x3f, sizeof f);
    for (int i = 0, x; i < k; ++i) {
        scanf("%d", &x); --x; 
        f[1 << i][x] = 0;
    }
    for (int s = 1; s < 1 << k; ++s) {
        for (int i = 0; i < n; ++i)
            for (int t = s - 1 & s; t; t = t - 1 & s)
                f[s][i] = min(f[s][i], f[t][i] + f[s ^ t][i]);
        dijkstra(s);
    }
    int ans = INF;
    for (int i = 0; i < n; ++i) ans = min(ans, f[(1 << k) - 1][i]);
    printf("%d\n", ans);
    return 0;
}

同余最短路

这是一个最短路的变式问题。可以用于求解在某个范围内有多少重量可以由若干物品的完全背包凑出，就是多少数值可以由一些给定的数 $b_i$ 由 $\sum a_i b_i(a_i\ge 0)$ 得到。

SPFA

模板。

墨墨突然对等式很感兴趣，他正在研究 $\sum_{i=1}^n a_ix_i=b$ 存在非负整数解的条件，他要求你编写一个程序，给定 $n, a_{1\dots n}, l, r$ ，求出有多少 $b\in[l,r]$ 可以使等式存在非负整数解。
$n \le 12$ ， $0 \le a_i \le 5\times 10^5$ ， $1 \le l \le r \le 10^{12}$ 。

我们可以发现，如果 $x$ 可以被表示出，那么 $x+ka_i(k>0)$ 就可以被表示出。因此我们找一个最小的 $a_1$ ，然后连 $j\rightarrow (j+a_i)\mod a_1$ 的长度为 $a_i$ 的边，然后我们从 $0$ 开始跑最短路。由于这里图的形态不太能特殊构造，因此使用 SPFA 往往会跑的更快。

答案的求解十分容易。 $[0,r]$ 的答案数量为：

$\sum_{i=0}^{a_1-1}\max\left\{0,\left\lfloor\frac{r-d_i}{a_1}\right\rfloor+1\right\}$

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int n, a[20];
i64 l, r, f[500005];
bool inq[500005];

int main(void) {
    scanf("%d%lld%lld", &n, &l, &r);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    sort(a + 1, a + n + 1); 
    memset(f, 0x3f, sizeof(f));
    queue<int> q; q.push(0); 
    f[0] = 0; inq[0] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = 2; i <= n; ++i) {
            int v = (u + a[i]) % a[1];
            if (f[v] > f[u] + a[i]) {
                f[v] = f[u] + a[i];
                if (!inq[v]) inq[v] = true, q.push(v);
            }
        }
    }
    i64 ans = 0;
    for (int i = 0; i < a[1]; ++i) {
        if (r >= f[i]) ans += (r - f[i]) / a[1] + 1;
        if (l - 1 >= f[i]) ans -= (l - 1 - f[i]) / a[1] + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

转两圈

回归同余最短路问题的本质，

广义圆方树

广义圆方树是刻画图上点的必经性的工具，可以描述任意两点之间的所有必经点，也就是会经过的割点。

概述

广义圆方树是定义在一般无向图上的一种树形结构，是 v-DCC 缩点之后的产物。本质上可以看成“缩边”，就是将原图上所有对刻画必经性无用的边去掉。

我们建出 v-DCC 的“代表点”并向 v-DCC 内部所有点连边，这样会形成一个菊花图。这个“代表点”称为“方点”，而原图中的所有点对应“圆点”。代码如下：

void tarjan(int x) {
    dfn[x] = low[x] = ++num; st[++tot] = x; 
    // 孤立点在圆方树上根本没有边，不需要特判
    for (int y : G[x]) 
        if (!dfn[y]) {
            tarjan(y); low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) { // 找到了一个以 x 为根的 v-DCC
                int z; ++n; // 新建一个方点
                do addedge(z = st[tot--], n); while (z != y); 
                addedge(x, n);
            }
        } 
        else low[x] = min(low[x], dfn[y]);
}

性质

它们是广义圆方树工作的基础，首先是 v-DCC 的引理：

引理：如果 $x$ 与 $y,z$ 均点双连通，但是 $y,z$ 不点双连通，那么 $x$ 是 $y,z$ 的必经点。

然后是广义圆方树的性质：

性质 1：圆点 $x$ 的度数为它所在的 v-DCC 个数。
性质 2：圆方树上只有圆点和方点之间有边。
性质 3：原图上直接相连的 $x,y$ 属于一个 v-DCC，而且如果这个 v-DCC 的大小为 $2$ ，那么 $(x,y)$ 是割边。

下面三个是用来做题的：

性质 4：圆点 $x$ 是叶子当且仅当它在原图上不是割点。

证明：如果 $x$ 是割点，那么 $x$ 至少属于两个 v-DCC，这样存在 $y,z$ 两点与 $x$ 都点双连通，但是 $y,z$ 不点双连通，因此 $x$ 是 $y,z$ 的必经点，这样它不是叶子。

性质 5：广义圆方树上删掉圆点 $x$ 后剩余节点的联通性与原图上删除 $x$ 相等。

证明：如果 $x$ 是叶子，也就是它不是割点，删除显然没有影响。如果它是原图的割点，比如说 $x$ 在圆方树上连接了 $y,z$ ，那么与 $y,z$ 所在的点双连通之间不在连通，与其割点的性质是一样的。

性质 6： $x,y$ 简单路径上的所有圆点就是原图中 $x,y$ 之间的所必经点。这是圆方树的核心性质。

模板，直接输出最小编号的圆点即可。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, node; 
int dfn[200005], low[200005], num, st[200005], tot;
vector<int> E[200005], G[400005];

void tarjan(int x) {
    dfn[x] = low[x] = ++num; st[++tot] = x; 
    for (int y : E[x])
        if (!dfn[y]) {
            tarjan(y); low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) {
                int z; G[++node].emplace_back(x); G[x].emplace_back(node); 
                do G[node].emplace_back(z = st[tot--]), G[z].emplace_back(node); while (y != z);
            }
        } else low[x] = min(low[x], dfn[y]);
}

int f[400005], dep[400005]; 
void dfs(int x, int fa) {
    f[x] = fa; dep[x] = dep[fa] + 1; 
    for (int y : G[x]) if (y != fa) dfs(y, x);
}

int main(void) {
    scanf("%d", &n); node = n; 
    for (int u, v; scanf("%d%d", &u, &v) == 2 && u; )
        E[u].emplace_back(v), E[v].emplace_back(u);
    tarjan(1); dfs(1, 0); 
    int a, b; scanf("%d%d", &a, &b); int ans = 1e9; 
    if (dep[a] < dep[b]) swap(a, b);
    while (dep[a] > dep[b]) if ((a = f[a]) != b) ans = min(ans, a);
    while (a != b) ans = min({ans, a = f[a], b = f[b]});
    if (ans > n) puts("No solution");
    else printf("%d\n", ans);
    return 0;
}

特殊图

Problemset

这里的题会很杂。

最短路问题

与最短路相关的问题。它们是图论中比较基础的内容，但是很有意思。

[NOI Online 2021 入门组] 重力球

Portal.

合法的位置不是很多，把它们都搜出来并标号，并求出每一个重力方向到达的位置编号来建图，就可以使用 bfs 来求最短路了。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f; 

int n, m, q, tot, d[2005][2005], id[305][305], t[2005][2005][4];
bool a[305][305];

inline bool check(int x, int y) {
    return a[x - 1][y] || a[x + 1][y] || a[x][y - 1] || a[x][y + 1];
}

vector<int> G[2005][4];
void bfs(void) {
    queue<pair<int, int>> q; 
    for (int i = 1; i <= tot; ++i) q.emplace(i, i), d[i][i] = 0;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        for (int k = 0; k < 4; ++k) for (int i : G[x][k]) for (int j : G[y][k])
            if (d[i][j] == INF) d[i][j] = d[x][y] + 1, q.emplace(i, j);
    }
}

int main(void) {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) a[0][i] = a[i][0] = a[n + 1][i] = a[i][n + 1] = 1;
    while (m--) { int x, y; scanf("%d%d", &x, &y); a[x][y] = 1; }

    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (!a[i][j] && check(i, j)) id[i][j] = ++tot;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) t[i][j][0] = a[i][j - 1] ? id[i][j] : t[i][j - 1][0], t[i][j][1] = a[i - 1][j] ? id[i][j] : t[i - 1][j][1];
    for (int i = n; i >= 1; --i) for (int j = n; j >= 1; --j) t[i][j][2] = a[i][j + 1] ? id[i][j] : t[i][j + 1][2], t[i][j][3] = a[i + 1][j] ? id[i][j] : t[i + 1][j][3];
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (id[i][j]) for (int k = 0; k < 4; ++k) G[t[i][j][k]][k].emplace_back(id[i][j]);

    memset(d, 0x3f, sizeof(d));
    bfs();

    while (q--) {
        int x, p, y, q; scanf("%d%d%d%d", &x, &y, &p, &q);
        if (x == p && y == q) puts("0");
        else {
            int ans = min({d[t[x][y][0]][t[p][q][0]], d[t[x][y][1]][t[p][q][1]], d[t[x][y][2]][t[p][q][2]], d[t[x][y][3]][t[p][q][3]]});
            printf("%d\n", ans == INF ? -1 : ans + 1);
        }
    }
    return 0;
}

[JLOI2015] 管道连接

Portal.

求的是最小斯坦纳树森林。设 $g(s)$ 代表连接 $s$ 所需要的最小代价，先用常规方法赋予初值，然后整一个子集 DP 进行更新。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

int n, m, p, f[1024][1005];
vector<pair<int, int>> G[1005];

queue<int> q; 
bool inq[1005];
void SPFA(int s) {
    for (int i = 0; i < n; ++i) if (f[s][i] != INF) q.emplace(i);
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (auto [v, w] : G[u]) if (f[s][v] > f[s][u] + w) 
            f[s][v] = f[s][u] + w, q.emplace(v), inq[v] = true;
    }
}

int solve(int k) {
    if (k == 0) return 0;
    for (int s = 1; s < 1 << k; ++s) {
        for (int t = s - 1 & s; t; t = t - 1 & s)
            for (int i = 0; i < n; ++i)
                f[s][i] = min(f[s][i], f[t][i] + f[s ^ t][i]);
        SPFA(s);
    }
    int ans = INF; 
    for (int i = 0; i < n; ++i) ans = min(ans, f[(1 << k) - 1][i]);
    return ans;
}

struct Node {
    int c, p, v; 
    bool operator < (const Node &a) const {
        return c < a.c;
    }
} a[15];
int g[1024];
int main(void) {
    scanf("%d%d%d", &n, &m, &p);
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        G[u].emplace_back(v, w); G[v].emplace_back(u, w);
    } 
    for (int i = 0; i < p; ++i) scanf("%d%d", &a[i].c, &a[i].p);
    sort(a, a + p); memset(g, 0x3f, sizeof(g)); g[0] = 0; int k = 0;
    for (int i = 0; i < p; ++i) {
        if (i == 0 || a[i].c != a[i - 1].c) ++k; 
        a[i].v = k - 1;
    }
    for (int i = 1; i < 1 << k; ++i) {
        memset(f, 0x3f, sizeof(f)); int cnt = 0;
        for (int j = 0; j < p; ++j) if (1 << a[j].v & i) f[1 << cnt++][a[j].p] = 0;
        g[i] = solve(cnt);
    }
    for (int i = 1; i < 1 << k; ++i)
        for (int j = i - 1 & i; j; j = j - 1 & i)
            g[i] = min(g[i], g[j] + g[i ^ j]);
    return printf("%d\n", g[(1 << k) - 1]), 0;
}

[ARC084B] Small Multiple

Portal.

任何数都可以从 $1$ 开始通过 $\times 10,+1$ 两种操作得到，代价分别是 $0,1$ 。跑一个 01 bfs 最短路求出 $f(i)$ 代表模 $K$ 为 $i$ 的数的最小代价即可。

查看代码

#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

bool vis[100005];
deque<pair<int, int>> q; 

int main(void) {
    int K; scanf("%d", &K);
    q.emplace_back(1, 1); vis[1] = true;
    while (!q.empty()) {
        int num = q.front().first, w = q.front().second; q.pop_front();
        if (num == 0) return printf("%d\n", w), 0;
        if (!vis[num * 10 % K]) q.emplace_front(num * 10 % K, w), vis[num * 10 % K] = true;
        if (!vis[(num + 1) % K]) q.emplace_back((num + 1) % K, w + 1);
    }
    return 0;
}

[省选联考 2021 A/B 卷] 图函数

Portal.

直接考虑整体的答案。发现只有 $u\le v$ ，经过的点的编号全部大于 $v$ 的点对（因为在这之前小于的都删完了） $(u,v)$ 才会有贡献。

发现这是个 Floyd 的模型，这样可以方便地统计路径上经过的最小编号的最大值。这样的时间复杂度为 $O(n^3+m)$ ，相当极限！因此注意 Floyd 枚举的时候如果距离没有就跳过，并且不要计算不合法的转移。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m, f[1005][1005]; // f[i][j]: i 到 j 的路径中，经过的最小编号的边的最大值 
int ans[200005]; 

int main(void) {
	scanf("%d%d", &n, &m); 
	for (int i = 1; i <= n; ++i) f[i][i] = m + 1; 
	for (int i = 1, u, v; i <= m; ++i) scanf("%d%d", &u, &v), f[u][v] = i; 
	for (int k = n; k >= 1; --k) { // 只经过 k ~ n 的点，路径上的点的编号大于 k 
		for (int i = 1; i <= n; ++i) if (f[i][k]) {
			int lim = i < k ? n : k - 1; // 当 i >= k, j >= k 时，经过 1 ~ k 是不合法的 
			for (int j = 1; j <= lim; ++j)
				f[i][j] = max(f[i][j], min(f[i][k], f[k][j])); 
		}
		for (int i = k; i <= n; ++i) { // k -> i, i -> k
			int t = min(f[k][i], f[i][k]); 
			if (t) ++ans[t - 1]; 
		}
	}
	for (int i = m; i >= 0; --i) ans[i] += ans[i + 1]; 
	for (int i = 0; i <= m; ++i) printf("%d ", ans[i]); 
	return putchar('\n'), 0; 
}

连通性问题

包括连通性中需要一些思考的综合题，以及圆方树相关题目。

[APIO2018] 铁人两项

Portal.

相当于是求 $(s,f)$ 上的简单路径上共有多少个点（除去 $s,f$ ）。

建立出圆方树。路径 $s$ 到 $f$ 对应是链上的权值和，其中方点的贡献为点双连通分量的大小，圆点的贡献为 $-1$ ，这样就是答案。因为方点计算贡献时，路径上的所有圆点都会被多算进去一次（两头是因为题目规定，中间的是因为两边都有方点）。

统计答案时采用 dfs，计算有多少个 $(s,f)$ 点对。

注意原图可能不联通。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

int n, node, m, a[200005], N; 
int dfn[100005], low[100005], num, tot, st[100005];
vector<int> E[100005], G[200005];

inline void addedge(int u, int v) {
    G[u].emplace_back(v); 
    G[v].emplace_back(u);
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num; st[++tot] = x; ++N; a[x] = -1; 
    for (int y : E[x]) 
        if (!dfn[y]) {
            tarjan(y); low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) {
                int z; addedge(++node, x); ++a[node];
                do addedge(z = st[tot--], node), ++a[node]; while (z != y); 
            }
        } else low[x] = min(low[x], dfn[y]);
}

i64 ans; int siz[200005]; 
void dfs(int x, int fa) {
    siz[x] = (x <= n); i64 cnt = 0; 
    for (int y : G[x]) if (y != fa) {
        dfs(y, x); cnt += 1ll * siz[x] * siz[y];
        siz[x] += siz[y]; 
    } cnt += 1ll * siz[x] * (N - siz[x]);
    ans += 1ll * a[x] * cnt * 2; 
}

int main(void) {
    scanf("%d%d", &n, &m); node = n; 
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        E[u].emplace_back(v); E[v].emplace_back(u);
    }
    for (int i = 1; i <= n; ++i) if (!dfn[i]) {
        N = tot = 0; 
        tarjan(i); dfs(i, 0);
    } return printf("%lld\n", ans), 0;
}

[COI2007] Policija

Portal.

第二问就是看 $c$ 是否在简单路径上。第一问首先这条边必须是割边，这条割边可以对应到一个方点，看这个方点是否在简单路径上。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m, node; 
int dfn[200005], low[100005], num, tot, st[100005];
vector<int> E[100005], G[200005];
map<pair<int, int>, int> B;

void tarjan(int x) {
    dfn[x] = low[x] = ++num; st[++tot] = x; 
    for (int y : E[x]) 
        if (!dfn[y]) {
            tarjan(y); low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y]) {
                G[x].emplace_back(++node); G[node].emplace_back(x);
                if (st[tot] == y) B[{x, y}] = node; 
                for (int z = 0; z != y; ) {
                    G[node].emplace_back(z = st[tot--]);
                    G[z].emplace_back(node);
                }
            }
        } else low[x] = min(low[x], dfn[y]);
}

int dep[200005], siz[200005], f[21][200005]; 
void dfs(int x, int fa) {
    dfn[x] = ++num; dep[x] = dep[f[0][x] = fa] + 1; siz[x] = 1;
    for (int i = 1; i <= 20; ++i) f[i][x] = f[i - 1][f[i - 1][x]];
    for (int y : G[x]) if (y != fa) { dfs(y, x); siz[x] += siz[y]; }
}
int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i >= 0; --i) if (dep[f[i][x]] >= dep[y]) x = f[i][x];
    if (x == y) return x; 
    for (int i = 20; i >= 0; --i) if (f[i][x] != f[i][y]) x = f[i][x], y = f[i][y]; 
    return f[0][x]; 
}
bool isanc(int x, int y) { // x 是否是 y 的祖先
    return dfn[x] <= dfn[y] && dfn[y] < dfn[x] + siz[x];
}
bool lie(int u, int v, int x) { // x 是否在 (u,v) 上
    if (!isanc(x, u) && !isanc(x, v)) return 0; 
    if (!isanc(LCA(u, v), x)) return 0; 
    return 1;
}

int main(void) {
    scanf("%d%d", &n, &m); node = n; 
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        E[u].emplace_back(v); E[v].emplace_back(u);
    } tarjan(1); num = 0; dfs(1, 0);
    int q; scanf("%d", &q); while (q--) {
        int op, a, b, c, d; scanf("%d%d%d%d", &op, &a, &b, &c);
        if (op == 1) {
            scanf("%d", &d); int e = -1; 
            auto it = B.find({c, d});
            if (it != B.end()) e = it->second;
            else {
                it = B.find({d, c});
                if (it != B.end()) e = it->second;
            }
            if (e == -1) puts("yes"); 
            else puts(lie(a, b, e) ? "no" : "yes"); 
        } else puts(lie(a, b, c) ? "no" : "yes");
    } 
    return 0;
}

[CF1763F] Edge Queries

Portal.

建立出圆方树。将原图中的每一条边对应到圆方树上，增加方点的权值。如果方点的权值为 $1$ ，那么说明是割边，否则删除任意一条都可以。这样答案就是路径上方点的权值和。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m, node, q; 
int dfn[400005], low[200005], num, st[200005], tot; 
vector<int> E[200005], G[400005]; 

void tarjan(int x) {
    dfn[x] = low[x] = ++num; st[++tot] = x; 
    for (int y : E[x])
        if (!dfn[y]) {
            tarjan(y); low[x] = min(low[x], low[y]); 
            if (dfn[x] <= low[y]) {
                G[++node].emplace_back(x); G[x].emplace_back(node); 
                for (int z = 0; z != y; ) {
                    G[node].emplace_back(z = st[tot--]); 
                    G[z].emplace_back(node); 
                }
            }
        } else low[x] = min(low[x], dfn[y]); 
}

int lg[400005], dep[400005], siz[400005], mi[22][400005], f[400005]; 
inline int get(int x, int y) { return dep[x] < dep[y] ? x : y; }
void dfs(int x, int fa) {
    f[x] = mi[0][dfn[x] = ++num] = fa; dep[x] = dep[fa] + 1; 
    for (int y : G[x]) if (y != fa) dfs(y, x);
}
int LCA(int u, int v) {
    if (u == v) return u; 
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v); 
    int k = lg[v - u]; 
    return get(mi[k][u + 1], mi[k][v - (1 << k) + 1]); 
}
int s[400005], w[400005];
void dfs2(int x) {
    s[x] = s[f[x]] + w[x]; 
    for (int y : G[x]) if (y != f[x]) dfs2(y);
}

int main(void) {
    scanf("%d%d", &n, &m); node = n; 
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        E[u].emplace_back(v); E[v].emplace_back(u); 
    } tarjan(1); num = 0; dfs(1, 0); 
    for (int i = 2; i <= node; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= lg[node]; ++i)
        for (int j = 1; j + (1 << i) - 1 <= node; ++j)
            mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);

    for (int u = 1; u <= n; ++u) for (int v : E[u]) if (u <= v) {
        if (f[u] == f[v]) ++w[f[u]]; 
        else if (f[f[u]] == v) ++w[f[u]]; 
        else ++w[f[v]];
    }
    for (int i = n + 1; i <= node; ++i) if (w[i] == 1) w[i] = 0;
    dfs2(1);

    for (scanf("%d", &q); q--; ) {
        int a, b; scanf("%d%d", &a, &b); int lca = LCA(a, b); 
        printf("%d\n", s[a] + s[b] - s[lca] - s[f[lca]]); 
    }
    return 0;
}

[CF487E] Tourists

Portal.

建立出圆方树，方点的权值是它所属的 v-DCC 内的最小值，然后线段树维护即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9; 

int n, m, q; 
int a[200005], dfn[200005], low[100005], num, tot, st[100005], node; 
vector<int> E[100005], G[200005]; 

inline void add(int u, int v) { G[u].emplace_back(v); G[v].emplace_back(u); }
void tarjan(int x) {
    dfn[x] = low[x] = ++num; st[++tot] = x; 
    for (int y : E[x]) if (!dfn[y]) {
        tarjan(y); low[x] = min(low[x], low[y]); 
        if (dfn[x] == low[y]) {
            int z; add(++node, x); 
            do add(z = st[tot--], node); while (z != y); 
        }
    } else low[x] = min(low[x], dfn[y]); 
}

int siz[200005], son[200005], f[200005], dep[200005], top[200005], idx[200005]; 
void dfs1(int x, int fa) {
    siz[x] = 1; dep[x] = dep[f[x] = fa] + 1; 
    for (int y : G[x]) if (y != fa) {
        dfs1(y, x); siz[x] += siz[y]; 
        if (siz[y] > siz[son[x]]) son[x] = y; 
    }
}
void dfs2(int x, int topf) {
    idx[dfn[x] = ++num] = x; top[x] = topf; 
    if (!son[x]) return; 
    dfs2(son[x], topf); 
    for (int y : G[x]) if (y != f[x] && y != son[x]) dfs2(y, y); 
}

int T[800005]; multiset<int> s[100005];
void build(int o, int l, int r) {
    if (l == r) return T[o] = a[idx[l]], void(); 
    int mid = l + r >> 1; 
    build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r); 
    T[o] = min(T[o << 1], T[o << 1 | 1]); 
}
void update(int o, int l, int r, int x, int k) {
    if (l == r) return T[o] = k, void(); 
    int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, k); 
    else update(o << 1 | 1, mid + 1, r, x, k); 
    T[o] = min(T[o << 1], T[o << 1 | 1]); 
}
int query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o]; 
    int mid = l + r >> 1, res = 1e9; 
    if (x <= mid) res = min(res, query(o << 1, l, mid, x, y)); 
    if (mid < y) res = min(res, query(o << 1 | 1, mid + 1, r, x, y)); 
    return res; 
}

int main(void) {
    scanf("%d%d%d", &n, &m, &q); node = n; 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        E[u].emplace_back(v), E[v].emplace_back(u); 
    } tarjan(1); num = 0; dfs1(1, 0); dfs2(1, 1); 
    for (int i = 2; i <= n; ++i) s[f[i] - n].insert(a[i]); 
    for (int i = n + 1; i <= node; ++i) a[i] = s[i - n].empty() ? INF : *s[i - n].begin(); 
    build(1, 1, node); 
    char op[5]; int x, y; 
    while (q--) {
        scanf("%s%d%d", op, &x, &y); 
        if (op[0] == 'C') {
            update(1, 1, node, dfn[x], y);
            if (x == 1) { a[x] = y; continue; }
            s[f[x] - n].erase(s[f[x] - n].find(a[x])); s[f[x] - n].insert(y); 
            a[f[x]] = *s[f[x] - n].begin(); a[x] = y; 
            update(1, 1, node, dfn[f[x]], a[f[x]]); 
        } else {
            int ans = INF; 
            while (top[x] != top[y]) {
                if (dep[top[x]] < dep[top[y]]) swap(x, y); 
                ans = min(ans, query(1, 1, node, dfn[top[x]], dfn[x])); 
                x = f[top[x]]; 
            }
            if (dep[x] > dep[y]) swap(x, y); 
            ans = min(ans, query(1, 1, node, dfn[x], dfn[y])); 
            if (x > n) ans = min(ans, a[f[x]]); 
            printf("%d\n", ans); 
        }
    }
    return 0;
}

图上乱搞

一些奇怪的问题。

[CSP-S 2022] 星战

Portal.

说的是所有点的出度为 $1$ ，但是这样不好维护，转化为入度进行维护，搞一个哈希提高正确率。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64; 

mt19937 Rand(time(0)); 

int n, m, q; 
u64 r[500005], g[500005]; // 入度，全部入度
u64 w[500005];

int main(void) {
    scanf("%d%d", &n, &m); u64 ans = 0, res = 0; 
    for (int i = 1; i <= n; ++i) ans += (w[i] = Rand()); 

    while (m--) {
        int u, v; scanf("%d%d", &u, &v); 
        r[v] += w[u]; g[v] = r[v]; 
        res += w[u]; 
    }

    for (scanf("%d", &q); q--; ) {
        int op, u, v; scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &u, &v); 
            r[v] -= w[u]; res -= w[u]; 
        } else if (op == 2) {
            scanf("%d", &v); 
            res -= r[v]; r[v] = 0; 
        } else if (op == 3) {
            scanf("%d%d", &u, &v); 
            r[v] += w[u]; res += w[u]; 
        } else {
            scanf("%d", &v); 
            res += g[v] - r[v]; r[v] = g[v]; 
        }
        puts(res == ans ? "YES" : "NO"); 
    }
    return 0;
}