XCPC wiki - 图论技巧集

转化为树——树边和非树边

回忆 Tarjan 里讲的有向图 DFS 生成树：

DFS 生成树 每当通过某条边访问到一个新节点，就加入这个点和这条边，并为点记录 DFS 序（unix 时间戳）。

DFS 生成树的边的种类：

• 树边 DFS 生成树上的边；
• 前向边 从某个点到它的某个子孙节点的边，产生了捷径。
• 反向边 从某个点到它的某个祖先节点的边，产生了环；
• 横叉边 从某个点到一个既非它子孙节点、也非它祖先节点的边，连接了两个强连通子图。

对于无向图是类似的，不同点是 无向图的 DFS 树没有横叉边 ，只有前向边和反向边，而前向边都是已访问的，可以认为 无向图的 DFS 树只有反向边，因此非树边的端点$u,v$ 的 LCA 为$v$，作树上差分时，直接$w_{v}-d,\ w_{u}+d$ 即可。

删边后的连通性

给定一个无向连通图。每次询问给出一组边，确定删除这些边后图是否连通。

令第$i$ 条非树边的权值是$2^i$，再令这条边的两个端点在树上的对应路径上的边全部$\oplus 2^i$。那么一个极小的割一定满足其中所有边的权值异或和为$0$，问题转化为询问集合是否存在一个异或为$0$ 的子集，可以用线性基解决。

ll w[N], d[N];
bool vis[N];
vector<pair<int, int>> E[N];
void dfs(int u, int p) {
    vis[u] = 1;
    for (auto& [v, id] : E[u]) {
        if (v == p) continue;
        if (!vis[v]) {
            dfs(v, u);
            d[u] ^= d[v];
            w[id] = d[v];
        }
        else if (!w[id]) {
            w[id] = rng();
            d[u] ^= w[id];
            d[v] ^= w[id];
        }
    }
}

void eachT() {
    int n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        E[u].emplace_back(v, i);
        E[v].emplace_back(u, i);
    }

    dfs(1, 0);

    for (int q = read(); q--;) {
        Hamel H;
        bool ok = 1;

        for (int c = read(); c--;) {
            int id = read();
            if (!H.insert(w[id])) ok = 0;
        }

        printf("%s\n", ok ? "Connected" : "Disconnected");
    }
}

变式：给定$n$ 个点、$n$ 条双向边的环。有$m$ 对点对$a_i,b_i$，要求删掉尽可能多的边，使得删完后，每对$a_i,b_i$ 仍联通。求出剩余边数的最小值。(CF1996G. Penacony)

void eachT() {
    int n = read(), m = read();

    vector<ull> f(n);

    while (m--) {
        int a = read() - 1, b = read() - 1;
        ull x = rng();
        f[a] ^= x, f[b] ^= x;  // 差分
    }

    for (int i = 1; i < n; ++i) {
        f[i] ^= f[i - 1];      // 前缀和
    }

    unordered_map<ull, int> cnt;

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, ++cnt[f[i]]);
    }
    printf("%d\n", n - ans);
}

删边后的二分性

题意 给定连通无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。

思路 二分图的充要条件：不存在奇环。如果图中存在奇环，我们需要删一条边破坏图中所有的奇环，那么答案是所有奇环的交集中的边。由于一个自交的奇环必然引出一个简单奇环，所以我们只需要考虑简单环。在 DFS 生成树上考虑。

定义：

• 本原环：只含有一条非树边的环。
• 覆盖：对于一条非树边，称其本原环中的树边被其覆盖。
• 奇边：形成的本原环是奇环的非树边。
• 偶边：形成的本原环是偶环的非树边。

注意到，答案边被所有奇边覆盖，如果不止一个本原奇环，那么答案边不会被偶边覆盖。因此，如果不止一个本原奇环，那么不被任何偶边覆盖，且被所有奇边覆盖的边，就是答案边。

两个特判：

• 原图本就为二分图：随意删除都可行；
• 只有一个本原奇环：唯一的非树边也是答案。

vector<pair<int, int>> E[N];
int dep[N], vis[N];
int w[N];    // 边权
int val[N];  // 点权 表示本原奇环 - 偶环数量
int cnt;     // 奇环数量
int spj;     // 产生本原奇环的非树边

void dfs1(int u) {
    vis[u] = 1;
    for (auto& [v, id] : E[u]) {
        if (!vis[v]) {  // 树边
            dep[v] = dep[u] + 1;
            w[id] = 1;
            dfs1(v);
        }
        else if (!w[id]) {  // 非树边
            w[id] = 1;
            if (dep[u] - dep[v] & 1) {  // 偶环
                --val[u], ++val[v];  // u-v 路径上偶环数量 +1
            }
            else {  // 奇环
                ++cnt;
                ++val[u], --val[v];  // u-v 路径上奇环数量 +1
                spj = id;  // 记录产生奇环的非树边
            }
        }
    }
}

vector<int> res;
void dfs2(int u) {
    vis[u] = 1;
    for (auto& [v, id] : E[u]) {
        if (!vis[v]) {
            dfs2(v);
            if (val[v] == cnt) res.push_back(id);  // 所有奇环经过的非树边
            val[u] += val[v];   // 树上差分的还原
        }
    }
}

void eachT() {
    int n = read(), m = read();

    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        E[u].emplace_back(v, i);
        E[v].emplace_back(u, i);
    }

    dfs1(1);
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    dfs2(1);

    // 无奇环 所有边都是答案
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; ++i)
            printf("%d ", i);
        return;
    }

    // 只有一个奇环 特判唯一的非树边也是答案
    if (cnt == 1) {
        res.push_back(spj);
    }

    printf("%lld\n", res.size());
    for (auto& i : res) {
        printf("%d ", i);
    }
}

转化为有向图——减小边数

无向图三元环计数

洛谷 P1989

int n, m;
cin >> n >> m;
vector<pair<int, int>> edge(m);
vector<int> deg(n);
for (auto& [u, v] : edge) {
    cin >> u >> v;
    u--, v--;
    deg[u]++, deg[v]++;
}

// 转化为有向图
vector<unordered_map<int, int>> adj(n);
vector<vector<int>> E(n);
for (auto& [u, v] : edge) {
    if (deg[u] > deg[v] || deg[u] == deg[v] && u < v) {
        swap(u, v);
    }
    E[u].push_back(v);
    adj[u][v] = 1;
}

ll res = 0;
for (int u = 0; u < n; ++u) {
    for (auto& v : E[u]) {  // 用 unordered_map 的 auto 会 T
        for (auto& w : E[v]) res += adj[u].count(w);
    }
}
cout << res << "\n";

子图的最小生成树

[[…/contests/2024 牛客多校 /2024-07-18：2024 牛客暑期多校训练营 2#*B. MST|2024-07-18：2024 牛客暑期多校训练营 2]]

void eachT() {
    int n = read(), m = read(), q = read();

    vector<tuple<int, int, int>> E(m);
    vector<int> deg(n);
    for (auto& [w, u, v] : E) {
        u = read() - 1, v = read() - 1;
        w = read();
        ++deg[u];
        ++deg[v];
    }

    // 转化为有向图
    vector<vector<pair<int, int>>> G(n);
    vector<unordered_map<int, int>> adj(n + 1);
    for (auto& [w, u, v] : E) {
        if (deg[u] > deg[v] || deg[u] == deg[v] && u < v) {
            swap(u, v);
        }
        G[u].emplace_back(w, v);
        adj[u][v] = w;
    }

    DSU dsu(n);  // 并查集开在外面

    while (q--) {
        int k = read();

        // DSU dsu(n);  // 开在里面会 T

        vector<int> node(k);
        unordered_map<int, int> vis;
        for (auto& u : node) {
            u = read() - 1;
            vis[u] = 1;

            // 用什么初始化什么
            dsu.p[u] = u;
            dsu.siz[u] = 1;
        }

        // 连边
        vector<tuple<int, int, int>> E;
        for (auto& u : node) {  // 用 unordered_map 的 auto 会 T
            for (auto& [w, v] : G[u]) {
                if (vis.count(v)) {
                    E.emplace_back(w, u, v);
                }
            }
        }
        sort(E.begin(), E.end());

        // Kruskal
        ll res = 0, cnt = 0;
        for (auto& [w, u, v] : E) {
            if (dsu.uno(u, v)) {
                res += w;
                cnt += 1;
            }
        }

        if (cnt != k - 1) res = -1;  // 不连通
        printf("%lld\n", res);
    }
}

ICPC2024 Xi’an I - The Last Cumulonimbus Cloud

void eachT() {
    int n = read(), m = read(), q = read();

    vector<vector<int>> E(n);
    vector<int> deg(n);
    while (m--) {
        int u = read() - 1, v = read() - 1;
        E[u].push_back(v);
        E[v].push_back(u);

        ++deg[u];
        ++deg[v];
    }

    queue<int> Q;
    vector<int> vis(n);
    for (int i = 0; i < n; ++i) {
        if (deg[i] <= 10) Q.push(i);
    }

    vector<vector<int> > G(n);
    while (!Q.empty()) {
        auto u = Q.front(); Q.pop();
        vis[u] = 1;

        for (auto& v : E[u]) {
            if (vis[v]) continue;
            G[u].push_back(v);
            if (--deg[v] == 10) Q.push(v);
        }
    }

    vector<int> a(n), f(n);
    for (int u = 0; u < n; ++u) {
        a[u] = read();
        for (auto& v : G[u]) {
            f[v] += a[u];
        }
    }

    while (q--) {
        int op = read(), u = read() - 1;

        if (op == 1) {
            int w = read();

            a[u] += w;
            for (auto& v : G[u]) {
                f[v] += w;
            }
        }
        else {
            int res = f[u];
            for (auto& v : G[u]) {
                res += a[v];
            }

            printf("%d\n", res);
        }
    }
}

2022MYCPCE - Hammer to Fall

constexpr int B = 3000, MOD = 998244353;
int n, m, q;
cin >> n >> m >> q;

vector<int> a(n);
for (int i = 0; i < n; ++i) {
    cin >> a[i];
}

vector<vector<pair<int, int>>> E(n);
while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    E[u].push_back({ w, v });
    E[v].push_back({ w, u });
}

vector<vector<pair<int, int>>> El(n);
vector<multiset<ll>> s(n);
for (int u = 0; u < n; ++u) {
    for (auto& [w, v] : E[u]) {
        s[u].insert(w);
        if (int(E[v].size()) > B) {
            El[u].push_back({ w, v });  // 所有点 -> 大点
        }
    }
}

vector<int> b(q);
for (int i = q - 1; i >= 0; --i) {
    cin >> b[i];
    b[i]--;
}

vector<ll> dp(n);
for (auto& u : b) {
    for (auto& [w, v] : El[u]) s[v].extract(dp[u] + w);  // s.extract(.) == s.erase(find(.))

    if (int(E[u].size()) <= B) {
        dp[u] = 8e18;
        for (auto& [w, v] : E[u]) {
            dp[u] = min(dp[u], dp[v] + w);
        }
    }
    else {
        dp[u] = *s[u].begin();
    }

    for (auto& [w, v] : El[u]) s[v].insert(dp[u] + w);
}

ll res = 0;
for (int i = 0; i < n; ++i) {
    res += a[i] * dp[i];
    res %= MOD;
}

cout << res << '\n';

数据随机

[[…/contests/2024 杭电多校 /2024-07-29：2024“钉耙编程”中国大学生算法设计超级联赛（4）|2024-07-29：2024“钉耙编程”中国大学生算法设计超级联赛（4）]]

题意 给定两个长度为$n$ 的序列$a_0,a_1,\dots,a_{n-1}$ 和$b_0,b_1,\dots,b_{n-1}$，你需要依次执行$q$ 次操作，每次操作将会给出一个整数$k$，对于每个$i$，你需要将$a_i$ 更新为$\max(a_i,b_{(i+k)\bmod n})$。为了证明你确实维护了$a$ 序列，请在每次操作之后输出$\sum_{i=0}^{n-1} a_i$ 的值。输入数据保证每个$a_i,b_i$ 都是在$[1,10^9]$ 均匀随机生成得到，且每个$k$ 都是在$[0,n)$ 均匀随机生成得到。(2024 杭电多校 4007 - 序列更新)

思路 取$\lim$ 为$b$ 中第$x$ 大元素，对于每次操作，考虑以下两种维护手法：

• 枚举$a$ 中所有值不超过$\lim$ 的下标$i$ ，用$b_{(i+k) \bmod n}$ 更新它。
• 枚举$b$ 中所有值大于$l i m$ 的下标$i$, 用它更新$a_{(i-k) \bmod n}$ 。时间复杂度$O(x)$ 。

由于数据随机，考虑计算$a$ 中一个位置期望需要经历多少次第一类操作，它的值才会大于$\lim$。假设经历了$i$ 次操作仍然不超过$\lim$，等价于$i+1$ 个随机数均不超过$\lim$ ，概率为$\left(1-\frac{x}{n}\right)^{i+1}$ ，故期望操作次数为：

$$\sum_{i \geq 0}\left(1-\frac{x}{n}\right)^{i+1} \approx \frac{1}{\frac{x}{n}}=\frac{n}{x}$$

综上可得期望时间复杂度为$O(\frac{n^2}{x}+n x)$, 当$x=\sqrt{n}$ 时为最优复杂度$O(n \sqrt{n})$。

void eachT() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n), b(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    auto c = b;
    sort(c.begin(), c.end());
    int lim = c[n - (int)sqrt(n)];

    vector<int> A, B;
    for (int i = 0; i < n; i++) {
        if (a[i] <= lim) A.push_back(i);
        if (b[i] > lim) B.push_back(i);
    }

    auto sol = [&](int x, int y) {
        if (a[x] >= b[y]) return;
        sum -= a[x];
        a[x] = b[y];
        sum += a[x];
    };

    while (q--) {
        int k;
        cin >> k;
        for (int j = 0; j < A.size();) {
            int& i = A[j];
            sol(i, (i + k) % n);
            if (a[i] > lim) {
                A[j] = A.back();
                A.pop_back();
            }
            else j++;
        }
        for (auto& i : B) {
            sol((i - k + n) % n, i);
        }
        cout << sum << "\n";
    }
}

转化为并查集——维护连通性

2023SDCPCJ. Not Another Path Query Problem

[[…/ 基础算法 /BITMASK#[2023SDCPCJ. Not Another Path Query Problem](https //codeforces.com/gym/104417/problem/J)|BITMASKS]]

CF891C. Envy

给定图 $G$。如果在图上跑最小生成树算法，只能得到一个 MST，这会令其他边嫉妒。因此，您会收到一些询问，每个询问包含图 $G$ 的一组边，确定是否存在包含所有这些边的最小生成树。

Input	Output
5 7 1 2 2 1 3 2 2 3 1 2 4 1 3 4 1 3 5 2 4 5 2 4 2 3 4 3 3 4 5 2 1 7 2 1 2	YES NO YES NO

Q1 只有一次询问，且这一次查询只有一条边：
只要用 kruskal 算法处理完所有边权小于这条边的边，此时如果这条边的两点已经在同一个连通块里了，那么这条边不可能在最小生成树里，反之则一定可以在某一个最小生成树里。

Q2 只有一次询问，且这一次查询有多条边：
依然按照边从小到大开始遍历，如果某一个边的两点已经在同一个连通块里了，那这条边不可能在最小生成树里，询问的答案是 NO。

Q3 多次询问，每次查询有多条边：
先存下所有的询问，然后按照边从小到大开始遍历，如果一组询问中有一条边不符合，那么这个询问就是 NO 的。

但是问题是对于正在查询的某一个边权，它可能存在在很多的查询中，那么就要 把每个查询分开讨论 了，对于包含某一个边权的某一组询问， 合并边的操作应当是临时的 ，不能影响其它询问，也就是合并这组询问里包含这一边权的边后，需要 回滚到合并前的状态 才能考虑下一组询问，这就要用到 可撤销并查集 了。

由于需要记录边的编号，不能对边排序，我们稍稍修改 kruskal 的代码：

struct Edge {
    int w, u, v;
};
Edge E[N];
map<int, vector<int> > mp;      // 权值为 w 的边的编号 Eid

int main() {
    int n = read(), m = read();
    for (int Eid = 1; Eid <= m; ++Eid) {
        E[Eid].u = read(), E[Eid].v = read(), E[Eid].w = read();
        mp[E[Eid].w].push_back(Eid);
    }

    DSU dsu(n);

    ll res = 0;  // 最小生成树的边权之和
    for (auto& [w, Ew] : mp) {  // 按权值从小到大遍历 Ew 是权值为 w 的边的编号
        for (int Eid : Ew) {
            if (dsu.uno(E[Eid].u, E[Eid].v))
                res += E[Eid].w;  // Kruskal 的合并
        }
    }

    printf("%lld\n", res);

    return 0;
}

加上对每个询问的处理：

struct Edge {
    int w, u, v;
};
Edge E[N];
map<int, vector<int>> mp;      // 权值为 w 的边的编号 Eid
map<int, vector<int>> que[N];  // 某一权值的边对应的询问 qid+ 边的编号 Eid
int ans[N];

int main() {
    int n = read(), m = read();
    for (int Eid = 1; Eid <= m; ++Eid) {
        E[Eid].u = read(), E[Eid].v = read(), E[Eid].w = read();
        mp[E[Eid].w].push_back(Eid);
    }

    DSU dsu(n);

    int q = read();
    for (int qid = 1; qid <= q; ++qid) {
        ans[qid] = 1;
        for (int k = read(); k--;) {
            int Eid = read();
            que[E[Eid].w][qid].push_back(Eid);
        }
    }

    ll res = 0;  // 最小生成树的边权之和
    for (auto& [w, Ew] : mp) {  // 按权值从小到大遍历 Ew 是权值为 w 的边的编号
        for (auto& [qid, Eq] : que[w]) {  // 某一权值的边对应的询问 qid+ 边的编号 Eq
            if (!ans[qid]) continue;      // 剪枝

            int h = dsu.history();  // 记录当前的状态

            for (auto& Eid : Eq) {
                if (!dsu.uno(E[Eid].u, E[Eid].v))  
                    ans[qid] = 0;  // 这条边的两点已经在同一个连通块里 询问为 NO
            }

            dsu.roll(h);  // 把刚才连的边全部撤销 回滚到之前的状态
        }

        for (int Eid : Ew) {
            if (dsu.uno(E[Eid].u, E[Eid].v))
                res += E[Eid].w;  // Kruskal 的合并
        }
    }

    for (int i = 1; i <= q; ++i) {
        printf("%s\n", ans[i] ? "YES" : "NO");
    }
}

例 3 给出$n$ 个点$m$ 条边的无向图，每个点有点权$h_i$。从点$i$ 走到点$j$ 会消耗$h_j-h_i$ 的能量（如果小于$0$ 就是恢复）。给出$q$ 个询问，每个询问包含起点$s$，终点$t$，能量$e$，能量值在移动的过程中不能低于$0$，问能否从$s$ 走到$t$。数据范围：$n,m,q \leqslant 2\times 10^5$。(CF1851G. Vlad and the Mountains)

问题转化为$s$ 到$t$ 路径上每个点$u$ 的点权$h_{u}-h_{s} \leqslant e$，即$h_{u} \leqslant h_{s} +e$，也就是$h_{\max} \leqslant h_{s} +e$，只需要检查只使用点权不超过$h_{s} +e$ 的点组成的子图上，$s,t$ 是否连通即可。离线询问，按点权大小加边。

int n, m;
cin >> n >> m;

vector<int> val(n);
for (int i = 0; i < n; i++) {
    cin >> val[i];
}

vector<int> pos(n);
iota(pos.begin(), pos.end(), 0);
sort(pos.begin(), pos.end(), [&](const int& u, const int& v) {
    return val[u] < val[v];
});

vector<vector<int>> g(n);
while (m--) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
}

int q;
cin >> q;

vector<array<int, 4>> que(q);
for (int i = 0; i < q; i++) {
    int u, v, e;
    cin >> u >> v >> e;
    u--, v--;
    que[i] = { e + val[u], u, v, i };
}
sort(que.begin(), que.end());

DSU dsu(n);
vector<int> ans(q);
int j = 0;
for (int i = 0; i < n; i++) {
    int u = pos[i];
    for (; j < q && que[j][0] < val[u]; j++) {
        ans[que[j][3]] |= dsu.same(que[j][1], que[j][2]);
    }
    for (auto v : g[u]) {
        if (val[v] <= val[u]) dsu.uno(u, v);
    }
}
for (; j < q; j++) {
    ans[que[j][3]] |= dsu.same(que[j][1], que[j][2]);
}

for (int i = 0; i < q; i++) {
    cout << (ans[i] ? "YES" : "NO") << "\n";
}
cout << "\n";

转化为线段树——区间连边

• 多个操作，每一个操作的影响范围是一个区间（时间区间，询问区间）。
• 多个询问，询问（某个时间时，某个操作后的）答案。

优化建图

有$n$ 个点，$q$ 个询问，每次询问给出一个操作，在这些操作后求$1$ 到$n$ 的最短路。$n \leqslant 1\times 10^{5},\ q \leqslant 1\times 10^{5}$。

• 1 u v w：连一条$u\to v$ 的有向边，权值为$w$；
• 2 u l r w：对于所有$i\in[l,r]$，连一条$u\to i$ 的有向边，权值为$w$；
• 3 u l r w：对于所有$i\in[l,r]$，连一条$i\to u$ 的有向边，权值为$w$；
• 4 l1 r1 l2 r2 w：对于所有$i\in[l_{1},r_{1}],j\in[l_{2},r_{2}]$，连一条$i\to j$ 的有向边，权值为$w$；

无论何种最短路方法，从建图就卡住了。注意到，题给建图是区间，联想到线段树，可以利用线段树减少连边数量，从而降低复杂度。

(洛谷 P6348 Journeys)

#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((L+R)>>1)
#define lson ls,L,mid
#define rson rs,mid,R

void eachT() {
    int n = read(), m = read(), st = read();
    st--;

    int N = (n << 3) + (m << 1);

    vector<int> num(n);
    vector<vector<pii>> E(N);
    auto build = [&](this auto&& self, int p, int L, int R) {
        E[p].push_back({ 0, p + (n << 2) });   // 正向节点连反向节点
        if (R - L < 2) return num[L] = p + (n << 2), void();
        E[p].push_back({ 0, ls });
        E[p].push_back({ 0, rs });
        E[ls + (n << 2)].push_back({ 0, p + (n << 2) });
        E[rs + (n << 2)].push_back({ 0, p + (n << 2) });
        self(lson), self(rson);
    };
    build(build, 1, 0, n);
    st = num[st];

    auto add_f = [&](this auto&& self, int l, int r, int w, int s, int p, int L, int R) {
        if (l <= L && R <= r) return E[s].push_back({ w, p });             // 虚拟点连正向节点
        if (l < mid) self(l, r, w, s, lson);
        if (mid < r) self(l, r, w, s, rson);
    };
    auto add_s = [&](this auto&& self, int l, int r, int w, int s, int p, int L, int R) {
        if (l <= L && R <= r) return E[p + (n << 2)].push_back({ w, s });  // 反向节点连虚拟点
        if (l < mid) self(l, r, w, s, lson);
        if (mid < r) self(l, r, w, s, rson);
    };
    for (int i = 0; i < m; ++i) {
        int l1 = read(), r1 = read(), l2 = read(), r2 = read();
        l1--, l2--;
        add_s(add_s, l1, r1, 1, (n << 3) + (i << 1), 1, 0, n);      // [l1,r1) -> 虚拟点 u
        add_f(add_f, l2, r2, 1, (n << 3) + (i << 1), 1, 0, n);      // 虚拟点 u -> [l2,r2)
        add_s(add_s, l2, r2, 1, (n << 3) + (i << 1 | 1), 1, 0, n);  // [l2,r2) -> 虚拟点 v
        add_f(add_f, l1, r1, 1, (n << 3) + (i << 1 | 1), 1, 0, n);  // 虚拟点 v -> [l1,r1)
    }

    vector<int> dis(N, 1e9), vis(N);
    dis[st] = 0;
    priority_queue<pii, vector<pii>, greater<>> Q;
    Q.push({ 0, st });
    while (!Q.empty()) {
        int u = Q.top().second; Q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (auto& [w, v] : E[u]) {
            if (vis[v]) continue;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({ dis[v],v });
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        printf("%d\n", dis[num[i]] >> 1);
    }
}

每时刻的二分性

给点一个$n$ 个节点的图，在$k$ 时间内有$m$ 条边会出现后消失，求出每一时间段内这个图是否是二分图。(洛谷 P5787 二分图)

输入$m$ 行，每行四个整数$x,y,\mathscr{l},r$，表示有一条连接$x,y$ 的边在$\mathscr{l}$ 时刻出现$r$ 时刻消失。

Input	Output
3 3 3 1 2 0 2 2 3 0 3 1 3 1 2	Yes No Yes

$0$ 时刻，出现两条边$(1,2)$ 和$(2,3)$。
第$1$ 时间段内，这个图是二分图，输出 Yes。
$1$ 时刻，出现一条边$(1,3)$。
第$2$ 时间段内，这个图不是二分图，输出 No。
$2$ 时刻，$(1,2)$ 和$(1,3)$ 两条边消失。
第$3$ 时间段内，只有一条边$(2,3)$，这个图是二分图，输出 Yes。

构建$\log k$ 层时间轴，形成一棵平衡二叉树，树上每个 节点  $\boldsymbol{p}$ 都代表一个 时间段 $\boldsymbol{[\mathscr{l},r]}$ 的某个性质，节点$p$ 的左右子节点的编号分别为 $2p$ 和 $2p+1$，分别储存时间段 $[\mathscr{l}, \mathrm{mid}]$ 和 $[\mathrm{mid}+1, r]$。

插入每一条边，转化为在$\log k$ 个时间段插入这一条边。

从根开始递归处理。处理左子树前，连上这个节点代表的边，处理左子树后，撤销连上的边，再处理右子树。递归到叶子时，时间段即是这一时刻，用扩展域并查集判断二分图。时间复杂度$\Theta(n\log k\log n)$。

struct DSU {};  // 可撤销并查集

#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((L+R)>>1)
#define lson ls,L,mid
#define rson rs,mid,R

void eachT() {
    int n = read(), m = read(), k = read();

    vector<vector<pii>> E(k << 2);
    auto update = [&](this auto&& self, int l, int r, pii x, int p, int L, int R) {
        if (l <= L && R <= r) return E[p].push_back(x);
        if (l < mid) self(l, r, x, lson);
        if (mid < r) self(l, r, x, rson);
    };
    while (m--) {
        int u = read(), v = read(), l = read(), r = read();
        if (l == r) continue;
        update(update, l, r, { u,　v }, 1, 0, k);
    }

    DSU dsu(2 * n);
    vector<int> ans(k);
    auto solve = [&](this auto&& self, int p, int L, int R) {
        int h = dsu.history();
        for (auto& [u, v] : E[p]) {
            if (dsu.same(u, v)) return dsu.roll(h);
            dsu.uno(u, v + n);
            dsu.uno(v, u + n);
        }
        if (R - L == 1) ans[L] = 1;
        else self(lson), self(rson);
        return dsu.roll(h);
    };
    solve(1, 0, k);
    
    for (int i = 0; i < k; i++) {
        printf("%s\n", ans[i] ? "Yes" : "No");
    }
}

每时刻的连通性

给点一个$n$ 个节点的图，在$k$ 时间内有$m$ 条边会出现后消失，求出每个节点与 1 连通的时间编号之和。(2024 杭电多选 1004 - 传送) ([[…/contests/2024 杭电多校 /2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）|2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）]])

天才的 lazytag：递归到叶时，对所在的连通块的根节点打上一个 lazytag，表示整个连通块需要加上一个值。假设$u$ 是$v$ 的祖先，断开$u,v$ 的话，需要将$v$ 加上$u$ 的 lazytag。连上$u,v$ 的话，需要将$v$ 减去$u$ 的 lazytag。

struct DSU {
    vector<int> p, siz;
    vector<ll> val;
    vector<pair<int&, int>> hp, hsiz;
    vector<pair<ll&, ll&>> hval;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        p.resize(n + 1);
        iota(p.begin(), p.end(), 0);
        siz.assign(n + 1, 1);
        val.assign(n + 1, 0);
    }

    int find(int x) {
        while (x != p[x]) x = p[x];  // 不能路径压缩
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool uno(int x, int y) {
        x = find(x), y = find(y);
        if (same(x, y)) return false;
        if (siz[x] < siz[y]) swap(x, y);  // 按秩启发式合并
        hsiz.push_back({ siz[x], siz[x] });
        siz[x] += siz[y];
        hp.push_back({ p[y], p[y] });
        p[y] = x;
        hval.push_back({ val[y], val[x] });
        val[y] -= val[x];
        return true;
    }

    int history() { return hp.size(); }  // 返回当前时间 h

    void roll(int h) {  // rollback 到 h
        while (hp.size() > h) {
            hp.back().first = hp.back().second;
            hp.pop_back();
            hsiz.back().first = hsiz.back().second;
            hsiz.pop_back();
            hval.back().first += hval.back().second;
            hval.pop_back();
        }
    }
};

#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((L+R)>>1)
#define lson ls,L,mid
#define rson rs,mid,R

void eachT() {
    int n = read(), m = read(), k = n;

    vector<vector<pii>> E(k << 2);
    auto update = [&](this auto&& self, int l, int r, pair<int, int> x, int p, int L, int R) {
        if (l <= L && R <= r) return E[p].push_back(x);
        if (l < mid) self(l, r, x, lson);
        if (mid < r) self(l, r, x, rson);
    };
    while (m--) {
        int u = read(), v = read(), l = read(), r = read();
        l--;
        if (u > v) swap(u, v);
        update(update, l, r, { u,v }, 1, 0, k);
    }

    DSU dsu(n);
    auto solve = [&](this auto&& self, int p, int L, int R) -> void {
        int h = dsu.history();
        for (auto& [u, v] : E[p]) {
            if (dsu.same(u, v)) continue;
            dsu.uno(u, v);
        }
        if (R - L < 2) dsu.val[dsu.find(1)] += L + 1;
        else self(lson), self(rson);
        return dsu.roll(h);
    };
    solve(1, 0, k);

    ll res = 0;
    for (int i = 1; i <= n; i++) {
        res ^= dsu.val[i];
    }
    printf("%lld\n", res);
}

删边后的二分性

给定连通无向图，可以从图中删除一条边，问删除哪些边可以使图变成一个二分图。(CF19E. Fairy)

int n = read(), m = read();

if (m == 0) {
    printf("0\n");
    return;
}

vector<pair<int, int>> E(m);
for (auto& [u, v] : E) {
    u = read(), v = read();
}

DSU dsu(n << 1);
vector<int> ans;
auto solve = [&](this auto&& self, int L, int R) {
    if (R - L < 2) return ans.push_back(L);

    int mid = L + R >> 1;
    int h = dsu.history(), keep = 1;
    for (int i = mid; i < R; ++i) {
        auto& [u, v] = E[i];
        if (dsu.same(u, v)) keep = 0;
        dsu.uno(u, v + n);
        dsu.uno(u + n, v);
    }
    if (keep) self(L, mid);
    dsu.roll(h);

    h = dsu.history(), keep = 1;
    for (int i = L; i < mid; ++i) {
        auto& [u, v] = E[i];
        if (dsu.same(u, v)) keep = 0;
        dsu.uno(u, v + n);
        dsu.uno(u + n, v);
    }
    if (keep) self(mid, R);
    return dsu.roll(h);
};
solve(0, m);

printf("%lld\n", ans.size());
for (auto x : ans) printf("%d ", x + 1);
printf("\n");

杂题

CF2023C. C+K+S

题意 给定两个强连通有向图，每个图都有恰好$n$ 个顶点，但可能有不同数量的边，保证这些图中任何一个环的长度都是$k$ 的倍数。已知每个顶点分为两种类型：出点或入点。

判断能否在原图之间添加恰好$n$ 条有向边，满足：

• 任何添加的边的两端都位于不同的图中，且是从出点指向入点；
• 在生成的图中，任何一个环的长度都是$k$ 的倍数。

思路 多数有向图的题目是暴力缩点，这题直接给出一个强连通分量，以前的方法不奏效了。

我们尝试从缩点的本质考虑。Tarjan 算法首先引入了 DFS 生成树，将边分为两类，树边和非树边，后者进一步分为前向边、反向边和横叉边。树是没有环的，对剩下的三组边分别讨论：（其中$d$ 表示树上节点的深度）

• 对于反向边$u\to v$，它直接与树边构成一个简单环，环长为$d_{u}-d_{v}+1$，它应当为$k$ 的倍数。
• 对于前向边和横叉边$u\to v$，它们没有直接构成一个环，而是产生了捷径，捷径的长度与树上路径的长度之差应当为$k$ 的倍数，于是有$k\mid d_{u}-d_{v}+1$。

总结：如果有一条非树边$u\to v$，必须满足$k\mid d_{u}-d_{v}+1$，即$d_{u}+1 \equiv d_{v} \pmod k$。

对于第一张图指向第二张图的边$u\to v$，需要保证$d_{u}+1 \equiv d_{v}+\Delta \pmod k$。为什么不是$d_{u}+1 \equiv d_{v} \pmod k$ 呢？因为选择不同的起点开始做 DFS 生成树，得到的每个点的深度是不同的，但它们的相对深度一样，所以需要加上一个位移量$\Delta$，这个$\Delta$ 可以是任意整数。

先统计每个深度下点的个数$\lbrace \operatorname{cnt}_{d_{u}} \rbrace$。只需要保证$d_{u}+1$ 的个数$\lbrace \operatorname{cnt}_{\text{图一, 出点},d_{u}+1} \rbrace$ 和$d_{v}$ 的个数$\lbrace \operatorname{cnt}_{\text{图二, 入点},d_{v}} \rbrace$ 这两个数组 循环位移相等 ，类似地，第二张图指向第一张图的边$v\to u$ 要满足$\lbrace \operatorname{cnt}_{\text{图二, 出点},d_{u}+1} \rbrace$ 和$d_{v}$ 的个数$\lbrace \operatorname{cnt}_{\text{图一, 入点},d_{v}} \rbrace$ 循环位移相等。

为了计算方便，代码中把两个数组$\operatorname{cnt}_{出}$ 和$\operatorname{cnt}_{入}$ 合并了，不合并也是可以的。对于第一张图，入点$+1$，出点$+n$，第二张图入点$+n$，出点$+1$。

判断两个数组循环位移相等是个经典问题，倍长后哈希 即可。

时间复杂度$\Theta(n)$。

（哈希模板来自：cup-pyy：一种比较科学的字符串哈希实现方法，略有修改）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ulll = __uint128_t;

constexpr int N = 1e6 + 8;
constexpr ull mod = (1ull << 61) - 1;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ull> dist(mod / 2, mod - 1);
const ull H = dist(rnd);

struct mull {
    ull x;
    constexpr mull(ull x = 0) : x{ norm(x) } {}
    constexpr ull norm(ull x) const { return x >= mod ? x - mod : x; }
    friend constexpr mull operator*(mull a, mull b) { return ulll(a.x) * b.x % mod; }
    friend constexpr mull operator+(mull a, mull b) { return a.norm(a.x + b.x); }
    friend constexpr mull operator-(mull a, mull b) { return a.norm(a.x + mod - b.x); }
    friend constexpr bool operator==(mull a, mull b) { return a.x == b.x; }
    friend constexpr bool operator!=(mull a, mull b) { return a.x != b.x; }
} power[N];

struct Hash {
    vector<int> s;
    vector<mull> h;
    Hash(const vector<int>& s) : s(s) {
        init(s);
    }
    void init(const vector<int>& s) {
        const int n = s.size();
        h.resize(n + 1);
        for (int i = 0; i < n; i++) {
            h[i + 1] = h[i] * H + s[i];
        }
    }
    mull operator()(int l, int r) {
        return h[r] - h[l] * power[r - l];
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    power[0] = 1;
    for (int i = 1; i < N; i++) {
        power[i] = power[i - 1] * H;
    }

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        int ocnt[2]{};  // 出点的个数
        auto solve = [&](int op) {
            vector<int> a(n);
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                ocnt[op] += a[i];
            }

            vector<vector<int>> E(n);
            int m;
            cin >> m;
            while (m--) {
                int u, v;
                cin >> u >> v;
                u--, v--;
                E[u].push_back(v);
            }

            vector<int> d(n, -1);
            auto dfs = [&](this auto&& self, int u) -> void {
                for (auto v : E[u]) {
                    if (d[v] != -1) continue;
                    d[v] = d[u] + 1;
                    self(v);
                }
            };
            dfs(0);

            // BFS 也可以
            // queue<int> Q;
            // Q.push(0);
            // d[0] = 0;
            // while (!Q.empty()) {
            //     int u = Q.front(); Q.pop();
            //     for (auto v : E[u]) {
            //         if (d[v] == -1) {
            //             d[v] = d[u] + 1;
            //             Q.push(v);
            //         }
            //     }
            // }

            vector<int> cnt(2 * k);
            for (int i = 0; i < n; i++) {
                cnt[(d[i] + a[i]) % k] += (a[i] ^ op) ? 1 : n;
            }
            for (int i = 0; i < k; i++) {
                cnt[i + k] = cnt[i];  // 倍长
            }
            return Hash(cnt);
        };

        auto L = solve(0);
        auto R = solve(1);
        
        bool ok = false;
        for (int i = 0; i < k; i++) {
            if (L(0, k) == R(i, i + k)) {
                ok = true;
            }
        }
        if (ocnt[0] == n || ocnt[1] == n) ok = true;  // 特判只有一种方向的边 没有增加环的数量 一定可行
        if (ocnt[0] + ocnt[1] != n) ok = false;       // 特判出入点数量不同

        cout << (ok ? "YES" : "NO") << "\n";
    }

    return 0;
}

VJspr7H - Johnny and Contribution

题意 给定一张$n$ 个点$m$ 条边的图，给每个点写上数字，其数字为所有相邻点的 MEX。请求出一种写数字的顺序使得编号为$i$ 的点上的数字为$t_i$。

如果题目有解，则一定满足：

1. 对于每个点，与之相邻的所有点的所有目标数字必定包含了$1\sim t_i-1$ 的所有数字。
2. 对于每个点，与之相邻的所有点的所有目标数字一定不包含$t_i$。

如果满足上述条件，则按照$t_i$ 从小到大写数字就是一个符合条件的顺序。

时间复杂度$\Theta(n)$。

int n = read(), m = read();

vector<vector<int>> E(n + 1);
while (m--) {
    int u = read(), v = read();
    E[u].push_back(v);
    E[v].push_back(u);
}

vector<int> tim(n + 1);
vector<vector<int>> vec(n + 1);
for (int i = 1; i <= n; ++i) {
    tim[i] = read();
    vec[tim[i]].push_back(i);
}

vector<int> ans;
bool ok = 1;
for (int time = 1; time <= n; ++time) {
    for (auto& v : vec[time]) {
        int mex = 1;

        unordered_map<int, bool> vis;
        for (auto& u : E[v]) vis[tim[u]] = 1;
        while (vis.count(mex)) ++mex;

        if (mex == tim[v]) ans.push_back(v);
        else ok = 0;
    }
}

if (!ok) printf("-1");
else for (auto it : ans) printf("%d ", it);

VJspr8G - 环境治理

题意$n$ 个点，两两相连，记$P=\sum \limits_{i=1}^{n} \sum \limits_{j=1}^{n} d(i,j)$。在第$i$ 天，与第$i\bmod n$ 相连的所有边的边权$-1$，但不得低于$L_{ij}$。问最少要经过多少天之后有$P \leq Q$。

思路 二分。

int n = read(), need = read();

vector dist(n + 1, vector<int>(n + 1, INTINF)), l(n + 1, vector<int>(n + 1));
vector dist2(n + 1, vector<int>(n + 1));

for (int i = 1; i <= n; ++i) {
    dist[i][i] = 0;
    for (int j = 1; j <= n; ++j)
        dist[i][j] = dist[j][i] = read();
}
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        l[i][j] = l[j][i] = read();

auto floyd = [&] {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist2[i][j] = min(dist2[i][j], dist2[i][k] + dist2[k][j]);
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            ans += dist2[i][j];
    return ans;
};

auto check = [&](int x) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            dist2[i][j] = max(l[i][j], dist[i][j] - x * 2);
    }
    return floyd() > need;
};

// 二分出大致范围
int lt = 0, rt = 2e5, mid = -1;
while (lt <= rt) mid = lt + rt >> 1, check(mid) ? lt = mid + 1 : rt = mid - 1;
rt = max(0, rt);

for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        dist[i][j] = max(l[i][j], dist[i][j] - rt * 2);

dist2 = dist;
if (floyd() <= need) return void(printf("%d\n", rt * 2));

for (int x = 0, pos = 1; x <= n * 2; ++x, pos = (pos + 1) % n, pos = pos == 0 ? n : pos) {
    for (int i = 1; i <= n; ++i) {
        dist[i][pos] = max(l[i][pos], dist[i][pos] - 1);
        dist[pos][i] = max(l[pos][i], dist[pos][i] - 1);
    }

    dist2 = dist;
    if (floyd() <= need) return void(printf("%d\n", x + 1 + rt * n));
}
printf("-1");