网站建设模板图片,广东建设信息网三库,东莞网站建设收费明细,网站开发软件系统G - Typical Path Problem
题目大意
给定一张 N N N 个点、 M M M 条边的简单无向图 G G G 和三个整数 A , B , C A,B,C A,B,C。
是否存在一条从顶点 A A A 到 C C C#xff0c;且经过 B B B 的简单路径#xff1f;
数据范围#xff1a; 3 ≤ N ≤ 2 1 0 5 3\le …G - Typical Path Problem
题目大意
给定一张 N N N 个点、 M M M 条边的简单无向图 G G G 和三个整数 A , B , C A,B,C A,B,C。
是否存在一条从顶点 A A A 到 C C C且经过 B B B 的简单路径
数据范围 3 ≤ N ≤ 2 × 1 0 5 3\le N\le 2\times 10^5 3≤N≤2×105 N − 1 ≤ M ≤ min ( N ( N − 1 ) 2 , 2 × 1 0 5 ) N-1\le M\le \min(\frac{N(N-1)}2,2\times 10^5) N−1≤M≤min(2N(N−1),2×105) 1 ≤ A , B , C ≤ N 1\le A,B,C\le N 1≤A,B,C≤N A , B , C A,B,C A,B,C 互不相同 什么是 简单路径 简单路径 是不重复经过同一个点的路径。例如 1 → 2 → 3 1\to 2\to 3 1→2→3 是简单路径但 1 → 2 → 1 1\to 2\to 1 1→2→1 不是简单路径。 解法1最大流
不难发现存在一条 A → B → C A\to B\to C A→B→C 的简单路径当且仅当存在一条 B → A B\to A B→A 和一条 B → C B\to C B→C 的路径使得这两条路径不经过同一个点 B B B 除外。因此我们可以构建网络流模型来解决此问题。
考虑由 ( 2 N 2 ) (2N2) (2N2) 个点组成的有向图 G ′ G G′
源点 s s s汇点 t t t G G G 中每个点对应的入点 x 1 , … , x N x_1,\dots,x_N x1,…,xN G G G 中每个点对应的出点 y 1 , … , y N y_1,\dots,y_N y1,…,yN
然后进行连边
对于每个 1 ≤ i ≤ N 1\le i\le N 1≤i≤N从入点 x i x_i xi 向出点 y i y_i yi 连接一条流量为 1 1 1 的边从源点 s s s 到中转点的入点 x B x_B xB 连接一条流量为 2 2 2 的边从 A A A 和 C C C 的出点 y A , y C y_A,y_C yA,yC 向汇点 t t t 分别连接一条流量为 1 1 1 的边最后 ∀ ( u , v ) ∈ E G \forall (u,v)\in E_G ∀(u,v)∈EG连接 y u → x v y_u \to x_v yu→xv 和 y v → x u y_v \to x_u yv→xu流量为 1 1 1。
计算 s s s 到 t t t 的最大流如果最大流为 2 2 2 则必定有存在不经过同一个顶点的 B → A , B → C B\to A,B\to C B→A,B→C 的路径。 证明 显然如果最大流为 2 2 2必然通过了 y A y_A yA 和 y C y_C yC 向汇点连接的边则一定分别有 B → A B\to A B→A 和 B → C B\to C B→C 的路径。 假设选择的这两条路径经过了同一顶点 v v v则两流都必须经过 x v → y v x_v\to y_v xv→yv 这一条流量为 1 1 1 的边此时最大流不可能超过 1 1 1。而最大流为 2 2 2说明假设不成立故没有经过同一顶点。 若使用 Dinic \text{Dinic} Dinic 算法由于最大流不超过 2 2 2网络流的时间复杂度为 O ( N M ) \mathcal O(NM) O(NM)。
代码实现
在以下的两种实现中我们规定
源点 s 0 s0 s0汇点 t 2 n 1 t2n1 t2n1 i i i 的入点 x i i x_ii xii i i i 的出点 y i n i y_ini yini
AC Library 实现
AtCoder Library 内置最大流的 Dinic \text{Dinic} Dinic 实现。
#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_graphint 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 i1; in; 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 手写实现 Dinic \text{Dinic} Dinic 算法对于此图的时间复杂度为 O ( N M ) \mathcal O(NM) O(NM)。如果不清楚算法原理可以参考 OI Wiki。 关于空间分配问题 由于新图 G ′ G G′ 包含 ( N 2 M 3 ) (N2M3) (N2M3) 条边若使用静态链式前向星存图数组大小需要开到 2 ( N 2 M 3 ) 2(N2M3) 2(N2M3)其理论最大值为 1.2 × 1 0 6 6 1.2\times 10^66 1.2×1066。此处建议使用 1.25 × 1 0 6 1.25\times 10^6 1.25×106 大小的数组。 #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];queueint q;q.push(s);while(!q.empty()){int v q.front(); q.pop();for(int ihead[v]; ~i; inxt[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 icur[v]; ~i flow; inxt[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 i1; in; 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 → C A\to C A→C 的任意简单路径。对于经过的每一个点双连通分量如果 B B B 在此点双内则必然存在 A → B → C A\to B\to C A→B→C 的简单路径如果 B B B 不属于任一经过的点双则不可能存在 A → B → C A\to B\to C A→B→C 的简单路径。
因此可以使用 Tarjan \text{Tarjan} Tarjan 算法构造原图的圆方树 T T T 来解决此问题。将上述算法转换到圆方树上如下
在 T T T 上找到 A → C A\to C A→C 的唯一简单路径。对于经过的每一个方点如果 B B B 是与其相邻的圆点则必然存在 A → B → C A\to B\to C A→B→C 的简单路径如果 B B B 不与任一经过的方点相邻则不可能存在 A → B → C A\to B\to C A→B→C 的简单路径。
总时间复杂度为 O ( N M ) \mathcal O(NM) O(NM)实际运行时间优于网络流解法。
代码实现
小贴士圆方树相关的数组要开到两倍大小不然会 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;
}vectorint G[maxn], T[maxn 1];inline void add_edge(vectorint* 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;
}总结
三种解法的对比参见下表
解法代码长度运行时间内存占用最大流AC Library1 523 B 523~\mathrm{B} 523 B 337 m s 337~\mathrm{ms} 337 ms 106480 K B 106480~\mathrm{KB} 106480 KB最大流Dinic2 1650 B 1650~\mathrm{B} 1650 B 334 m s 334~\mathrm{ms} 334 ms 46980 K B 46980~\mathrm{KB} 46980 KB圆方树3 1142 B 1142~\mathrm{B} 1142 B 162 m s 162~\mathrm{ms} 162 ms 57824 K B 57824~\mathrm{KB} 57824 KB
可见圆方树算法的运行速度最快最大流AC Library的代码最短最大流Dinic的内存占用最小。 个人评价 这道题出得很好题意简单而内涵丰富。 我赛时甚至没想到还可以网络流 https://atcoder.jp/contests/abc318/submissions/45209577 ↩︎ https://atcoder.jp/contests/abc318/submissions/45212257 ↩︎ https://atcoder.jp/contests/abc318/submissions/45210151 ↩︎
