连通性问题

· · 算法·理论

DFS 树

对图 G 进行 DFS,连边 \text{fa}_u \to u 形成 DFS 生成树。生成树上的边称作树边,其余边称作非树边。

按照 DFS 遍历顺序赋 DFS 序,记作 \text{dfn}_u。

E-DCC

对无向图 G,定义 \text{low}_u 为 v \in \text{subtree}(u) 且 v 通过非树边连向 u 的 \text{dfn}_v 最小值。对 (u,v) \in E 分讨:

转移是 chkmin。数组 \text{low}_u 刻画了 u 向外扩展的能力。

显然,割边 / 桥必然是树边。

定理 对 v \in \text{son}(u),边 (u,v) 是割边,当且仅当 \text{dfn}_u<\text{low}_v。

理解 条件表明 v 在不经过 v \to u 的情况下,无法到达比 u 更早访问的点。

将桥删去后,所有连通块构成 E-DCC,DFS 一次即可求解。

不妨设 G 连通,将 E-DCC 缩成一个点,新图必然是一棵树。边双缩点将图上边双问题转化为树上问题。

算法实现时,注意若有重边则应记录 \text{fa}_u \to u 边的标号。复杂度 O(n+m)。

:::::info[P8436 代码]

const int N = 5e5 + 5;
int n, m;
vector<pair<int, int>> e[N];

int dn, dfn[N], low[N], cut[4*N];
void tarjan(int u, int f) {
    dfn[u] = low[u] = ++dn;
    for (auto [v, id] : e[u]) {
        if (id == f) continue;
        if (!dfn[v]) {
            tarjan(v, id), chkmin(low[u], low[v]);
            if (low[v] > dfn[u]) cut[id] = true;
        } else {
            chkmin(low[u], dfn[v]);
        }
    }
}
int cnt, bel[N];
vector<int> dcc[N];
void dfs(int u, int x) {
    bel[u] = x, dcc[x].pb(u);
    for (auto [v, id] : e[u]) 
        if (!bel[v] && !cut[id]) dfs(v, x);
}

void _main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].pb(v, i), e[v].pb(u, i);
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1);
    for (int i = 1; i <= n; i++) if (!bel[i]) dfs(i, ++cnt);
    cout << cnt << '\n';
    for (int i = 1; i <= cnt; i++) {
        cout << dcc[i].size() << ' ';
        for (int u : dcc[i]) cout << u << ' ';
        cout << '\n';
    }
} 

:::::

V-DCC

定理 非根节点 u 是割点,当且仅当 \exists v \in \text{son}(u), \text{dfn}_u \le \text{low}_v。

注意特判 DFS 树根是割点的情形。实现略简单一些,可以不考虑重边。

V-DCC 比 E-DCC 复杂一些,因为割点同时属于多个点双。

求解 V-DCC 需要维护一个栈,将首次访问的点入栈。若 \text{dfn}_u \le \text{low}_v 成立,则弹栈直到 v 被弹出,被弹出的点与 u 构成 V-DCC。注意特判孤立点。

复杂度 O(n+m)。

:::::info[P8435 代码]

const int N = 5e5 + 5;
int n, m;
vector<int> e[N];

int dn, dfn[N], low[N], cut[N];
stack<int> st;
int cnt; vector<int> dcc[N];
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dn, st.emplace(u);
    int son = 0, deg = 0;
    for (int v : e[u]) if (v != u && v != fa) {
        deg++;
        if (!dfn[v]) {
            tarjan(v, u), chkmin(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                if (fa != -1 || ++son > 1) cut[u] = true;
                cnt++; int x;
                do x = st.top(), st.pop(), dcc[cnt].pb(x); while (x != v);
                dcc[cnt].pb(u);
            }
        } else {
            chkmin(low[u], dfn[v]);
        }
    }
    if (deg == 0 && fa == -1) dcc[++cnt].pb(u);
}

void _main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].pb(v), e[v].pb(u);
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, -1);
    cout << cnt << '\n';
    for (int i = 1; i <= cnt; i++) {
        cout << dcc[i].size() << ' ';
        for (int u : dcc[i]) cout << u << ' ';
        cout << '\n';
    }
}

:::::

Menger 定理

Menger 定理

本质是最大流最小割定理。边形式 Menger 定理视作 u \leadsto v 的最大流等于最小割,点形式 Menger 定理可以拆点。

不加证明地,给出 Menger 定理的如下推论:

推论 1 对 E-DCC 内任意两点 u,v,必存在经过 u,v 的回路。

推论 2(Robbins 定理)连通分量可定向为 SCC,当且仅当连通分量是 E-DCC。

推论 3(Whitney 定理)对 V-DCC 内任意两点 u,v,必存在经过 u,v 的简单环。

推论 4 对 n \ge 3 的 V-DCC 内任意两点 u,v,必存在经过 u,v 的简单 \ge 3 元环。

推论 5 对 n \ge 3 的 V-DCC 内任意点 u 和任意边 e,必存在经过 u,e 的简单环。

推论 6 对 n \ge 3 的 V-DCC 内任意两点 u,v 和任意边 e,必存在 u \leadsto e \leadsto v 的简单路径。

推论 7 对 n \ge 3 的 V-DCC 内任意三点 u,v,w,必存在 u \leadsto w \leadsto v 的简单路径。

SCC

Tarjan

有向图 DFS 树形成若干森林,不同 DFS 树必然不强连通,故只要讨论一棵 DFS 树。

维护一个栈,将首次访问的节点入栈。有向图上微调 \text{low} 的转移:

可以证明,若回溯前 \text{dfn}_u=\text{low}_u,则连续弹栈直到 x,栈内所有点构成 SCC。复杂度 O(n+m)。

将所有 SCC 缩成一个点,新图必然是 DAG。需要说明,Tarjan 得到的 SCC 标号是缩点的逆拓扑序。

:::::info[B3609 代码]

const int N = 1e4 + 5;
int n, m;
vector<int> e[N];

int dn, dfn[N], low[N], ins[N];
stack<int> st;
int cnt, bel[N]; vector<int> scc[N];
void tarjan(int u) {
    dfn[u] = low[u] = ++dn, st.emplace(u), ins[u] = true;
    for (int v : e[u]) {
        if (!dfn[v]) tarjan(v), chkmin(low[u], low[v]);
        else if (ins[v]) chkmin(low[u], dfn[v]);
    }
    if (dfn[u] != low[u]) return;
    int x; cnt++;
    do x = st.top(), st.pop(), ins[x] = false, 
        bel[x] = cnt, scc[cnt].pb(x);
    while (x != u);
}

bool vis[N];
void _main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) cin >> u >> v, e[u].pb(v);
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
    cout << cnt << '\n';
    for (int i = 1; i <= n; i++) {
        int x = bel[i];
        if (vis[x]) continue;
        sort(all(scc[x]));
        for (int u : scc[x]) cout << u << ' ';
        cout << '\n'; vis[x] = true;
    }
} 

:::::

Kosaraju

直接进行两次 DFS:

复杂度 O(n+m)。优势是只需 DFS,在特殊情形下优于 Tarjan:

:::::info[B3609 代码]

const int N = 1e4 + 5;
int n, m;
vector<int> e[N], e1[N];

int num, cnt, vis[N], seq[N], bel[N];
vector<int> scc[N];
void dfs1(int u) {
    vis[u] = true;
    for (int v : e[u]) if (!vis[v]) dfs1(v);
    seq[++num] = u;
}
void dfs2(int u, int x) {
    bel[u] = x, scc[x].pb(u);
    for (int v : e1[u]) if (!bel[v]) dfs2(v, x);
}

void _main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].pb(v), e1[v].pb(u);
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) dfs1(i);
    reverse(seq + 1, seq + n + 1);
    for (int i = 1; i <= n; i++) 
        if (!bel[seq[i]]) dfs2(seq[i], ++cnt);
    cout << cnt << '\n';
    fill(vis + 1, vis + n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x = bel[i]; 
        if (vis[x]) continue;
        sort(all(scc[x]));
        for (int u : scc[x]) cout << u << ' ';
        cout << '\n'; vis[x] = true;
    }
} 

:::::

2-SAT

熟知 k-SAT 问题中 k \ge 3 是 NPC 的。

2-SAT 问题 给定 m 条二元 boolean 方程,对 boolean 变量 x_1 \sim x_n 赋值满足所有约束,或报告无解。

有向边 i \to j 表达 x_i \Rightarrow x_j 的逻辑关系,形式化地 \lnot x_i \lor x_j。

将每个变量拆成 x_i 和 \lnot x_i 两个点,节点表示 x_i=0/1 的决策。可以得到下面的表格

方程 逻辑 建图
\lnot x_i \lor x_j x_i \Rightarrow x_j i \to j
\lnot x_i \lor \lnot x_j x_i \Rightarrow \lnot x_j i \to j'
x_i \lor x_j \lnot x_i \Rightarrow x_j i' \to j
x_i \lor \lnot x_j \lnot x_i \Rightarrow \lnot x_j i' \to j'

每条方程 a \lor b 可以建出两条有向边。

对有向图缩 SCC,若 x_i 与 \lnot x_i 强连通则 2-SAT 无解。

结论 若 2-SAT 有解,取 x_i 和 \lnot x_i 中拓扑序较大者为真是合法解。

求解 2-SAT 的复杂度为建图 & 缩 SCC 的复杂度。

特别地,若求 2-SAT 字典序最小解,可以逐位贪心,令 x_i=0 并检查是否矛盾。

圆方树

圆方树刻画了 V-DCC 缩点后的结构,将无向图必经性转化为树上问题。

我们用方点来代表一个点双,在方点下挂圆点表示 V-DCC 中的点,局部形成一个菊花。

对于广义圆方树,我们要求圆点和方点间隔连接。以 OI-Wiki 图解为例

我们有下述圆方树结构的基本性质:

圆方树刻画了无向图的必经性,下面给出叙述:

定理 对于圆点 u,v,树链 u \to v 上所有圆点恰为 u \leadsto v 的必经点。毛毛虫 u \to v 的虫足为 u \leadsto v 的可经点。

刻画 E-DCC 和 V-DCC 是容易的:

建立圆方树只要对 Tarjan 求点双进行微调,下面给出代码。

:::::info[代码]

int dn, cnt, dfn[N], low[N];
stack<int> st;
int add(int u, int v);  // 圆方树边 (u, v)
void tarjan(int u) {
    dfn[u] = low[u] = ++dn, st.emplace(u);
    for (int v : e[u]) {
        if (!dfn[v]) {
            tarjan(v), chkmin(low[u], low[v]);
            if (low[v] != dfn[u]) continue;
            int x; add(u, ++cnt);
            do x = st.top(), st.pop(), add(x, cnt);
            while (x != v);
        } else {
            chkmin(low[u], dfn[v]);
        }
    }
}

:::::

练习

CF1325F Ehab's Last Theorem

给出一个 n 个点 m 条边的连通无向图,找到一个大小为 \lceil\sqrt{n}\rceil 的独立集,或者一个大小不小于 \lceil\sqrt{n}\rceil 的环,输出构造。

:::::success[题解] 考虑拉出一棵 DFS 生成树,如果存在一条返祖边,其端点深度差 \ge\lceil\sqrt{n}\rceil-1,那么就找到了一个满足要求的环,直接输出即可。

反之考虑按深度模 \lceil\sqrt{n}\rceil-1 分成若干同余类,由于返祖边的性质,这些同余类一定都是独立集。感性理解一下,所有集合中必然存在至少一个满足要求的集合,于是做完了。

复杂度 O(n+m)。代码。

P6954 [NEERC 2017] Connections

给定一张 n 个点 m 条边的强连通有向图,保证 n \ge 4 \land m>2n。你需要保留恰好 2n 条边,使图仍然强连通,输出构造。

多测,\sum m \le 10^5,3 秒,512 MB。

:::::success[题解]

任取一点 x,在正反图上以 x 为根求出两棵外向 DFS 生成树 T_1,T_2。

注意到 e(T_1) 保证 x 可达任意点,e(T_2) 保证任意点可达 x。取 T_1 \cup T_2,从 x 中转则任意点对强连通,边数 2n-2。

复杂度 O(n+m)。代码。

:::::

CF1519E Off by One

给定 n 个点 (x_i,y_i),每个点可以变成 (x_i+1,y_i) 或 (x_i,y_i+1)。若 (0,0),(x_i,y_i),(x_j,y_j) 三点共线则可以匹配 i,j 并删去。求最大匹配,并输出一组方案。

:::::success[题解]

直观的想法是若 i,j 可以匹配就连边 i\leftrightarrow j,求一般图最大匹配,显然不可做。

进行点边转化,将斜率视作顶点,点视作边。记 u_i=\frac{y_i}{x_i+1},v_i=\frac{y_i+1}{x_i},将输入的每个点都视作 u_i\leftrightarrow v_i 的无向边。那么这张图的线图就是上面那个做法建出来的图。

问题是 L(G) 的最大匹配,转化到 G 上得到如下问题:最多能匹配多少对共顶点的边,每条边只能使用一次。

对 G 的全体连通块考虑,下面设 G 连通。理论上界是 \left\lfloor|E|/2\right\rfloor,我们断言上界可以取到,下面给出构造式证明:

拉出一棵 DFS 树,自底向上贪心。设计函数 dfs(u) 返回 u 子树内,未能匹配的那一条边,都匹配则返回无效值。遍历 u 的出边 e=(u,v),进行讨论:

遍历结束后,将被保留的 e 两两任意配对。显然最终剩余至多 1 条边,作为 DFS 的返回值即可。

总复杂度 O(n\log n)。代码。

:::::

CF555E Case of Computer Network

给出一个 n 个点 m 条边的无向图。给定 k 对节点 (u_i,v_i),你需要将所有边定向,使得任意 u_i \leadsto v_i 可达。判定是否存在可行方案。

:::::success[题解]

Robbins 定理 连通分量可定向为 SCC,当且仅当连通分量是 E-DCC。

对原图缩 E-DCC 得到一棵树。判掉 u_i,v_i 不连通的情形,则 u_i \to v_i 树链上边的方向确定为 \uparrow 或 \downarrow。

使用树上差分标记方向,若某条边同时确定为 \uparrow 和 \downarrow 则无解。

复杂度 O(m+n\log n),瓶颈在 LCA。代码。

:::::

QOJ15449 Finances

现有 n 个人,第 i 个人持有 a_i 元,负数表示债务,保证 \sum\limits_{i=1}^n a_i=0。记 A=\sum \limits_{i=1}^n \max(0,a_i)。

给定 m 条交易关系 (u,v,c),表示 u \leftrightarrow v 之间可以相互转账,总额度不超过 c。保证关系网连通,任意边 c \ge \lceil A/2 \rceil。

求若干次转账后能否使得每人持有 0 元。

多测,\sum n ,\sum m \le 10^6,3 秒,1024 MB。

:::::success[题解]

注意到 c \ge \lceil A/2 \rceil。若 u \leadsto v 存在 2 条边不交路径,则可以令每条边分摊不超过 A/2 的额度,中间节点净变化为 0。故 E-DCC 内任意两点必能平衡。

边双缩点,新点权值 b_u 定义为 E-DCC 点权和,转化为树上问题。

对 v \in \text{son}(u) 求得子树权值和 s_v=\sum \limits_{i \in \text{subtree}(v)} b_i,条件 |s_u| \le c(u,v) 是必要的。这个条件也是充分的,自底向上转账即可。

对树一次 DFS 即可判定。总复杂度 O(n+m)。代码。

:::::

P3225 [HNOI2012] 矿场搭建

给定一个 n 个点 m 条边的连通无向图。你需要设置若干关键点,使得任意一个点删掉后,其余点总能到达一个关键点。

输出关键点的最少数目,以及达成此数目的方案数。保证答案 < 2^{64}。

:::::success[题解] 考虑求出所有割点。此时对于一个大小为 k 的 V-DCC:

复杂度 O(n+m)。

QOJ14810 Trajan Algorithm

有错误的求割点「Trajan 算法」,问题在于返祖边转移 \text{low}_u \gets \text{low}_v。给定一张 n 个点 m 条边无向图,出边顺序确定,求会被错判的所有点。

多测,\sum n, \sum m \le 10^6,2 秒,1024 MB。

:::::success[题解]

割点判定定理是 \exists v \in \text{son}(u), \text{dfn}_u \le \text{low}_v。假算令 \text{low} 更小,故只会判漏割点。

考察下图所示的情形:

标准 Tarjan 算法令 \text{low}_x \gets \text{dfn}_a,假算改为 \text{low}_x \gets \text{low}_a。而 a 存在返祖边 a \to 1,于是 \text{low}_a<\text{dfn}_a。假算在 x \to a 处合并,从而

\text{low}_x\le \text{low}_a<\text{dfn}_a

而 DFS 回溯时 \text{low} 沿树边合并,这样 \text{low}_x 一路传回 a 的儿子 c,使得 \text{low}_c<\text{dfn}_a。

在 a 处进行割点判定需要 \text{low}_c\ge \text{dfn}_a,于是 a 作为割点被判漏。综上所述,得到结论

结论 割点 a 被判漏,当且仅当以 a 为根时,a 的每个子树内存在一条指向 a 的返祖边。

等价表述是,a 同时属于 \ge 2 个 V-DCC,这些点双内有 \ge 2 条连向 a 的边。求出所有 V-DCC 后容易判定。

复杂度 O(n+m)。

:::::

P9697 [GDCPC 2023] Canvas

现有长为 n 的序列 a_i,初始 a_i=0。给定 m 次操作 (u_i,v_i,x_i,y_i),保证 x_i,y_i \in \{1,2\}。操作令 a_{u_i} \gets x_i, a_{v_i} \gets y_i。

你可以按任意顺序执行操作,最大化 \sum \limits_{i=1}^n a_i 并输出构造。

多测,\sum n,\sum m \le 5 \times 10^5,3 秒,1024 MB。

:::::success[题解]

时光倒流,将覆盖操作转化为,首次操作后数值固定不变。

不难发现 (1,1) 操作最后做,(2,2) 操作最先做,只需考察 (1,2) 操作的顺序。

不妨设 x_i=1,y_i=2,连边 u_i \to v_i。分析一些特殊情况:

对有向图进行 SCC 缩点,按缩点后拓扑序操作即可。注意零入度 SCC 的根节点尽量选择 (2,2) 操作的点,这样可以让整个分量都是 2。

复杂度 O(n+m)。代码。

:::::

QOJ2214 Link Cut Digraph

维护一张 n 个点初始无边的有向图,进行 m 次加边,每次操作后求出强连通点对数。

:::::success[题解]

设 T(e) 为边 e 出现时刻,f(e) 为边 e=(u,v) 端点 u \leftrightsquigarrow v 强连通的最早时刻。

对时间轴升序扫描,若 f(e) \ge T(e) 则在 f(e) 时刻加入双向边 u \leftrightarrow v。原图 SCC 等效于当前图的连通块,并查集维护 \sum \binom{\text{siz}_i}{2} 即可。

问题转化为求每条边 e 的 f 值。将操作离线后时间轴分治,设分治区间 [l,r],分治中心为 m。

对分治区间上的边 G_1=(V,E_{[l,r]}) 缩 SCC,则 u \leftrightsquigarrow v 在 G_1 中强连通当且仅当 f(e)\le m。取 e \in E 分讨:

每条边 e 只会划分到一侧,从而 \log 层分治树上 \sum |E| \le O(m\log m)。

注意精细实现,只遍历 E_{[l,r]} 端点,用 Tarjan 求 SCC 可以做到 O(|E|) 复杂度。下传右侧边时只关心 SCC 的闭合时刻,故将端点改为 SCC 标号。

总复杂度 O(m \log m)。代码。

:::::

CF1989F Simultaneous Coloring

现有一个 n \times m 的网格,你可以将一列涂黑,或者将一行涂白。

每轮可以同时进行 k 次操作,代价为 [k>1]k^2。对于同时受到两类操作影响的格子,颜色可以自由选定。

进行 q 次操作,给定 (x,y,c),增加一条限制,格子 (x,y) 必须涂成颜色 c。每次操作后,输出满足所有要求的最小代价。

:::::success[题解]

显然行列至多操作一次。设第 i 行的操作时刻为 x_i,第 j 行的操作时刻为 y_j,钦定 (i,j) 为白等价于 x_i \le y_j,为黑等价于 x_i \ge y_j。

考虑用 n+m 个虚点代表行列,边的方向代表偏序关系。若 (i,j) 为白则连边 i \to j+n,为黑则连边 j+n \to i。

分析可得,最优策略一定是对每个 SCC 整体操作,再按缩点后拓扑序依次操作。答案即为所有 SCC 点数平方和。

离线时间轴分治求出每条边的闭合时刻 f(e),对时间轴扫描线,SCC 转化为无向图连通块,并查集胡乱维护即可。

视 n,m,q 同阶复杂度 O(n \log n)。代码。

:::::

P9139 [THUPC 2023 初赛] 喵了个喵 II

给定一个长为 4n 的序列,其中 1\sim n 各出现 4 次。你需要将其划分为两个相等的子序列,输出构造或报告无解。

:::::success[题解]

考虑问题的弱化,即 1 \sim n 各出现 2 次。设数值 i 两次出现的位置为 l_i,r_i,其中 l_i<r_i,则有

结论 无解当且仅当 \exists i \ne j, [l_i,r_i] \subseteq [l_j,r_j]。

1221 和 1212 是很好的例子。如果有解,则只要将 l_i 分为一组,r_i 分为一组。

受上述讨论启发,记数值 i 四次出现的位置依次为 p_{0,i},p_{1,i},p_{2,i},p_{3,i}。讨论可行的划分方式:

实际上,我们只要关注前两种划分方案。设布尔变量 x_i 表示选择何种方案,将 x_i=1 代表的方案写作 [l_{i,1},r_{i,1}], [l_{i,2},r_{i,2}]。根据无解条件,我们添加下列约束:

这是一个 2-SAT 问题。对约束中的 i,j,连边 x_i \to \neg x_j, x_j \to \neg x_i 后缩 SCC,直接做可得到 O(n^2) 复杂度。

转二维平面分析,则 [l_1,r_1]\subseteq [l_2,r_2] 相当于 (l_1,r_1) 落在一个 2-side 矩形内:

可以做主席树优化建图,或者 CDQ 分治套前缀优化建图,Tarjan 求解复杂度 O(n \log n)。CDQ 代码。

不过我们还有一种更聪明的手法,可以使用 Kosaraju 求 SCC,这样只要两次 DFS。考虑这篇文章中提及的技巧,假设节点 u 代表区间 A=[l_1,r_1],我们希望找到 B=[l_2,r_2] 作为 u 的后继节点 v,且 v 未访问。

使用线段树维护左端点 l,节点维护区间内未访问的 r 的最小 & 最大值。若 B \subseteq A 则在 [l_1,r_1] 上查 r_{\min},若 A \subseteq B 则在 [1,l_1] 上查 r_{\max}。访问 B 前将 B 代表的区间删去。

注意两次 DFS 时正反图的对应关系。复杂度仍为 O(n \log n) 但空间线性。代码。

:::::

CF487E Tourists

给定一张 n 个点 m 条边的无向连通图,点带权 w_i。进行 q 次操作:

  • 给定 i,x,令 w_i \gets x。
  • 给定 u,v,查询 u \leadsto v 所有简单路径中,点权 \min 的最小值。

:::::success[题解]

两个 \min 的方向相同,可以去掉一个,问题变为 u \leadsto v 可经点的权值 \min。

建立广义圆方树,转化为单点修改,链 1- 邻域点权 \min。魔怔一点可以毛毛虫剖分维护。

我们将圆点权值挂在邻域方点上,在方点处用 multiset 记最小值,只要使用普通树剖套线段树解决。复杂度 O(q \log^2 n)。

:::::

P16136 [ICPC 2018 NAIPC] Winter Festival

给定一张 n 个点 m 条边的无向图。你需要将边赋一组权 w(e),满足下列条件:

  • 边权 w(e) \in \{0,1,2\}。
  • 对任意简单环 C,\sum \limits_{e \in C} w(e) \equiv 1 \pmod 2。
  • 对任意点 u 的任意出边 e_1,e_2,(w(e_1)+w(e_2)) \bmod3 \ne 1。

最小化 \sum \limits_{e \in E} w(e) 并输出,或报告无解。

:::::success[题解]

性质 有解的必要条件是 G 是边仙人掌。

证明 设简单环 C_1,C_2 公共路径为 P。分别设路径 P,C_1 \setminus P, C_2\setminus P 的边权和为 w_1,w_2,w_3。由约束得

w_1+w_2 \equiv 1 \pmod 2\\ w_2+w_3 \equiv 1 \pmod 2\\ w_1+w_3 \equiv 1 \pmod 2

三式相加得

2(w_1+w_2+w_3) \equiv 1 \pmod 2

左式显然为偶数,矛盾。故原图必为边仙人掌。

建立原图的广义圆方树,并在圆方树上 DP。设 f_{u,S} 表示满足下列条件的最小代价:

设方点 v 传递数组 h_{v,T} 表示,处理子树后父边颜色集合为 T 的最小代价。圆点处的转移是简单的:

f'_{S \cup T} \gets f_{S}+h_{v,T}

为方便书写,定义两个辅助量,对圆点 u

\begin{aligned} A_u(x)&=\min_{S \cup \{x\} \text{ is valid}} f_{u,S}\\ A_u(x,y)&=\min_{S \cup \{x,y\} \text{ is valid}} f_{u,S}\\ \end{aligned}

意义是方点父亲接 1/2 条边的代价。对边仙人掌,方点必定为桥或简单环,下面讨论方点 DP。

若方点 p 代表桥 u \to v,转移是容易的:

h_{p,\{x\}}=x+A_v(x)

若方点 p 代表环 u \to v_1 \to v_2 \to \cdots \to v_k \to u,枚举 w(u,v_1)=a \in \{0,1,2\} 断环为链。做一个线性 DP:

初始 DP 令 f_{u,\varnothing}=0,其余位置 +\infty。所求为 \min\limits_{S} f_{\text{root},S}。

总复杂度 O(|\Sigma|n+m),其中 |\Sigma| 表示状态数和转移数。代码。

:::::

P8456 「SWTR-8」地地铁铁

给定一张 n 个点 m 条边的无向连通图,每条边染为黑色或白色。求点对 (x,y) 的数目,存在简单路径 x\leadsto y 有两种颜色。

P10140 [USACO24JAN] Island Vacation P