G - Typical Path Problem

題目大意

給定一張 $N$ 個點、$M$ 條邊的簡單無向圖 $G$ 和三個整數(shù) $A,B,C$。

是否存在一條從頂點 $A$ 到 $C$，且經(jīng)過 $B$ 的簡單路徑？

數(shù)據(jù)范圍：

• $3\le N\le 2\times 10^5$
• $N?1\le M\le \min (\frac{N(N?1)}{2},2\times 10^5)$
• $1\le A,B,C\le N$（$A,B,C$ 互不相同）

什么是 簡單路徑 ？
簡單路徑 是不重復(fù)經(jīng)過同一個點的路徑。例如，$1\to 2\to 3$ 是簡單路徑，但 $1\to 2\to 1$ 不是簡單路徑。

解法1：最大流

不難發(fā)現(xiàn)，存在一條 $A\to B\to C$ 的簡單路徑，當(dāng)且僅當(dāng)存在一條 $B\to A$ 和一條 $B\to C$ 的路徑，使得這兩條路徑不經(jīng)過同一個點（$B$ 除外）。因此，我們可以構(gòu)建網(wǎng)絡(luò)流模型來解決此問題。

考慮由 $(2N+2)$ 個點組成的有向圖 $G^{\prime }$：

• 源點：$s$
• 匯點：$t$
• $G$ 中每個點對應(yīng)的入點：$x_1,\dots ,x_N$
• $G$ 中每個點對應(yīng)的出點：$y_1,\dots ,y_N$

然后進行連邊：

• 對于每個 $1\le i\le N$，從入點 $x_i$ 向出點 $y_i$ 連接一條流量為 $1$ 的邊；
• 從源點 $s$ 到中轉(zhuǎn)點的入點 $x_B$ 連接一條流量為 $2$ 的邊；
• 從 $A$ 和 $C$ 的出點 $y_A,y_C$ 向匯點 $t$ 分別連接一條流量為 $1$ 的邊；
• 最后，$?(u,v)\in E_G$，連接 $y_u\to x_v$ 和 $y_v\to x_u$，流量為 $1$。

計算 $s$ 到 $t$ 的最大流，如果最大流為 $2$ 則必定有存在不經(jīng)過同一個頂點的 $B\to A,B\to C$ 的路徑。

證明
顯然，如果最大流為 $2$，必然通過了 $y_A$ 和 $y_C$ 向匯點連接的邊，則一定分別有 $B\to A$ 和 $B\to C$ 的路徑。
假設(shè)選擇的這兩條路徑經(jīng)過了同一頂點 $v$，則兩流都必須經(jīng)過 $x_v\to y_v$ 這一條流量為 $1$ 的邊，此時最大流不可能超過 $1$。而最大流為 $2$，說明假設(shè)不成立，故沒有經(jīng)過同一頂點。

若使用 $\text{Dinic}$ 算法，由于最大流不超過 $2$，網(wǎng)絡(luò)流的時間復(fù)雜度為 $\mathcal{O}(N+M)$。

代碼實現(xiàn)

在以下的兩種實現(xiàn)中，我們規(guī)定

• 源點：$s=0$
• 匯點：$t=2n+1$
• $i$ 的入點：$x_i=i$
• $i$ 的出點：$y_i=n+i$

AC Library 實現(xiàn)

AtCoder Library 內(nèi)置最大流的 $\text{Dinic}$ 實現(xiàn)。

#include <cstdio>
#include <atcoder/maxflow>
using namespace std;int main()
{int n, m, a, b, c;scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);int s = 0, t = (n << 1) + 1;atcoder::mf_graph<int> G(t + 1);G.add_edge(s, b + n, 2);G.add_edge(a + n, t, 1);G.add_edge(c + n, t, 1);for(int i=1; i<=n; i++)G.add_edge(i, i + n, 1);while(m--){int x, y;scanf("%d%d", &x, &y);G.add_edge(x + n, y, 1);G.add_edge(y + n, x, 1);}puts(G.flow(s, t, 2) == 2? "Yes": "No");return 0;
}

Dinic 手寫實現(xiàn)

$\text{Dinic}$ 算法對于此圖的時間復(fù)雜度為 $\mathcal{O}(N+M)$。如果不清楚算法原理可以參考 OI Wiki。

關(guān)于空間分配問題
由于新圖 $G^{\prime }$ 包含 $(N+2M+3)$ 條邊，若使用靜態(tài)鏈?zhǔn)角跋蛐谴鎴D，數(shù)組大小需要開到 $2(N+2M+3)$，其理論最大值為 $1.2\times 10^6+6$。此處建議使用 $1.25\times 10^6$ 大小的數(shù)組。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxn 400005
#define maxm 1250005
using namespace std;int n, s, t, head[maxn], cur[maxn], dis[maxn],cnt, w[maxm], to[maxm], nxt[maxm];inline void add(int u, int v, int flow)
{nxt[cnt] = head[u];head[u] = cnt;to[cnt] = v;w[cnt++] = flow;
}inline void add_flow(int u, int v, int f)
{add(u, v, f);add(v, u, 0);
}inline bool bfs()
{memset(dis, -1, sizeof(int) * n);dis[s] = 0, cur[s] = head[s];queue<int> q;q.push(s);while(!q.empty()){int v = q.front(); q.pop();for(int i=head[v]; ~i; i=nxt[i])if(w[i]){int u = to[i];if(dis[u] == -1){dis[u] = dis[v] + 1, cur[u] = head[u];if(u == t) return true;q.push(u);}}}return false;
}int dfs(int v, int flow)
{if(v == t) return flow;int res = 0;for(int i=cur[v]; ~i && flow; i=nxt[i]){cur[v] = i;int u = to[i];if(w[i] && dis[u] == dis[v] + 1){int k = dfs(u, min(flow, w[i]));w[i] -= k;w[i ^ 1] += k;flow -= k;res += k;}}return res;
}int main()
{int n, m, a, b, c;scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);s = 0, t = (n << 1) + 1, ::n = t + 1;memset(head, -1, sizeof(int) * ::n);add_flow(s, b + n, 2);add_flow(a + n, t, 1);add_flow(c + n, t, 1);for(int i=1; i<=n; i++)add_flow(i, i + n, 1);while(m--){int x, y;scanf("%d%d", &x, &y);add_flow(x + n, y, 1);add_flow(y + n, x, 1);}int mf = 0;while(bfs()) mf += dfs(s, 2);puts(mf == 2? "Yes": "No");return 0;
}

解法2：圓方樹

注意到以下算法的正確性：

• 找到 $A\to C$ 的任意簡單路徑。對于經(jīng)過的每一個點雙連通分量，如果 $B$ 在此點雙內(nèi)，則必然存在 $A\to B\to C$ 的簡單路徑；如果 $B$ 不屬于任一經(jīng)過的點雙，則不可能存在 $A\to B\to C$ 的簡單路徑。

因此，可以使用 $\text{Tarjan}$ 算法構(gòu)造原圖的圓方樹 $T$ 來解決此問題。將上述算法轉(zhuǎn)換到圓方樹上如下：

• 在 $T$ 上找到 $A\to C$ 的唯一簡單路徑。對于經(jīng)過的每一個方點，如果 $B$ 是與其相鄰的圓點，則必然存在 $A\to B\to C$ 的簡單路徑；如果 $B$ 不與任一經(jīng)過的方點相鄰，則不可能存在 $A\to B\to C$ 的簡單路徑。

總時間復(fù)雜度為 $\mathcal{O}(N+M)$，實際運行時間優(yōu)于網(wǎng)絡(luò)流解法。

代碼實現(xiàn)

小貼士：圓方樹相關(guān)的數(shù)組要開到兩倍大小，不然會 RE 哦~

#include <cstdio>
#include <cstdlib>
#include <vector>
#define maxn 200005
using namespace std;inline void setmin(int& x, int y)
{if(y < x) x = y;
}vector<int> G[maxn], T[maxn << 1];inline void add_edge(vector<int>* G, int x, int y)
{G[x].push_back(y);G[y].push_back(x);
}int dfc, dfn[maxn], low[maxn], top, st[maxn], cnt;void tarjan(int v)
{low[v] = dfn[v] = ++dfc;st[++top] = v;for(int u: G[v])if(!dfn[u]){tarjan(u);setmin(low[v], low[u]);if(low[u] == dfn[v]){add_edge(T, v, ++cnt);do add_edge(T, st[top], cnt);while(st[top--] != u);}}else setmin(low[v], dfn[u]);
}int n, m, a, b, c, ct[maxn << 1];
void dfs(int v, int par)
{if(v > n)for(int u: T[v])ct[u] ++;if(v == c){puts(ct[b]? "Yes": "No");exit(0);}for(int u: T[v])if(u != par)dfs(u, v);if(v > n)for(int u: T[v])ct[u] --;
}int main()
{scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);while(m--){int x, y;scanf("%d%d", &x, &y);add_edge(G, x, y);}cnt = n;tarjan(1);dfs(a, -1);return 0;
}

總結(jié)

三種解法的對比參見下表：

解法	代碼長度	運行時間	內(nèi)存占用
最大流（AC Library）1	$523\mathrm{B}$	$337\mathrm{ms}$	$106480\mathrm{KB}$
最大流（Dinic）2	$1650\mathrm{B}$	$334\mathrm{ms}$	$46980\mathrm{KB}$
圓方樹3	$1142\mathrm{B}$	$162\mathrm{ms}$	$57824\mathrm{KB}$

可見，圓方樹算法的運行速度最快，最大流（AC Library）的代碼最短，最大流（Dinic）的內(nèi)存占用最小。

個人評價
這道題出得很好，題意簡單而內(nèi)涵豐富。
我賽時甚至沒想到還可以網(wǎng)絡(luò)流

---

1. https://atcoder.jp/contests/abc318/submissions/45209577 ??

2. https://atcoder.jp/contests/abc318/submissions/45212257 ??

3. https://atcoder.jp/contests/abc318/submissions/45210151 ??