首页 > 其他分享 >AtCoder Beginner Contest 318 G - Typical Path Problem 题解

AtCoder Beginner Contest 318 G - Typical Path Problem 题解

时间:2024-09-08 23:25:19浏览次数:11  
标签:AtCoder 318 int 题解 d% 路径 add maxn include

G - Typical Path Problem

题目大意

给定一张 \(N\) 个点、\(M\) 条边的简单无向图 \(G\) 和三个整数 \(A,B,C\)。

是否存在一条从顶点 \(A\) 到 \(C\),且经过 \(B\) 的简单路径?

数据范围:

  • \(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\) 互不相同)

什么是 简单路径
简单路径 是不重复经过同一个点的路径。例如,\(1\to 2\to 3\) 是简单路径,但 \(1\to 2\to 1\) 不是简单路径。

解法1:最大流

不难发现,存在一条 \(A\to B\to C\) 的简单路径,当且仅当存在一条 \(B\to A\) 和一条 \(B\to C\) 的路径,使得这两条路径不经过同一个点(\(B\) 除外)。因此,我们可以构建网络流模型来解决此问题。

考虑由 \((2N+2)\) 个点组成的有向图 \(G'\):

  • 源点:\(s\)
  • 汇点:\(t\)
  • \(G\) 中每个点对应的入点:\(x_1,\dots,x_N\)
  • \(G\) 中每个点对应的出点:\(y_1,\dots,y_N\)

然后进行连边:

  • 对于每个 \(1\le i\le N\),从入点 \(x_i\) 向出点 \(y_i\) 连接一条流量为 \(1\) 的边;
  • 从源点 \(s\) 到中转点的入点 \(x_B\) 连接一条流量为 \(2\) 的边;
  • 从 \(A\) 和 \(C\) 的出点 \(y_A,y_C\) 向汇点 \(t\) 分别连接一条流量为 \(1\) 的边;
  • 最后,\(\forall (u,v)\in E_G\),连接 \(y_u \to x_v\) 和 \(y_v \to x_u\),流量为 \(1\)。

计算 \(s\) 到 \(t\) 的最大流,如果最大流为 \(2\) 则必定有存在不经过同一个顶点的 \(B\to A,B\to C\) 的路径。

证明
显然,如果最大流为 \(2\),必然通过了 \(y_A\) 和 \(y_C\) 向汇点连接的边,则一定分别有 \(B\to A\) 和 \(B\to C\) 的路径。
假设选择的这两条路径经过了同一顶点 \(v\),则两流都必须经过 \(x_v\to y_v\) 这一条流量为 \(1\) 的边,此时最大流不可能超过 \(1\)。而最大流为 \(2\),说明假设不成立,故没有经过同一顶点。

若使用 \(\text{Dinic}\) 算法,由于最大流不超过 \(2\),网络流的时间复杂度为 \(\mathcal O(N+M)\)。

代码实现

在以下的两种实现中,我们规定

  • 源点:\(s=0\)
  • 汇点:\(t=2n+1\)
  • \(i\) 的入点:\(x_i=i\)
  • \(i\) 的出点:\(y_i=n+i\)

AC Library 实现

AtCoder Library 内置最大流的 \(\text{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_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 手写实现

\(\text{Dinic}\) 算法对于此图的时间复杂度为 \(\mathcal O(N+M)\)。如果不清楚算法原理可以参考 OI Wiki

关于空间分配问题
由于新图 \(G'\) 包含 \((N+2M+3)\) 条边,若使用静态链式前向星存图,数组大小需要开到 \(2(N+2M+3)\),其理论最大值为 \(1.2\times 10^6+6\)。此处建议使用 \(1.25\times 10^6\) 大小的数组。

#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\) 的任意简单路径。对于经过的每一个点双连通分量,如果 \(B\) 在此点双内,则必然存在 \(A\to B\to C\) 的简单路径;如果 \(B\) 不属于任一经过的点双,则不可能存在 \(A\to B\to C\) 的简单路径。

因此,可以使用 \(\text{Tarjan}\) 算法构造原图的圆方树 \(T\) 来解决此问题。将上述算法转换到圆方树上如下:

  • 在 \(T\) 上找到 \(A\to C\) 的唯一简单路径。对于经过的每一个方点,如果 \(B\) 是与其相邻的圆点,则必然存在 \(A\to B\to C\) 的简单路径;如果 \(B\) 不与任一经过的方点相邻,则不可能存在 \(A\to B\to C\) 的简单路径。

总时间复杂度为 \(\mathcal O(N+M)\),实际运行时间优于网络流解法。

代码实现

小贴士:圆方树相关的数组要开到两倍大小,不然会 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;
}

总结

三种解法的对比参见下表:

解法 代码长度 运行时间 内存占用
最大流(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)的内存占用最小。

个人评价
这道题出得很好,题意简单而内涵丰富。
我赛时甚至没想到还可以网络流


  1. https://atcoder.jp/contests/abc318/submissions/45209577 ↩︎

  2. https://atcoder.jp/contests/abc318/submissions/45212257 ↩︎

  3. https://atcoder.jp/contests/abc318/submissions/45210151 ↩︎

标签:AtCoder,318,int,题解,d%,路径,add,maxn,include
From: https://www.cnblogs.com/stanleys/p/18403712/abc318

相关文章

  • UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
    A-ChristmasPresent题目大意给定两个正整数\(B,G\)(\(1\leB,G\le1000\)且\(B\neG\)),判断哪个更大。分析模拟即可。代码#include<cstdio>usingnamespacestd;intmain(){ intb,g; scanf("%d%d",&b,&g); puts(b>g?"Bat":&qu......
  • 洛谷 P9754 [CSP-S 2023] 结构体 题解
    题目传送门洛谷博客CSDNCSP-S2023T3结构体题解基本思路本题主要考查编码能力,所以直接给出基本思路:由于可以递归式的创建元素,最多可以同时存在\(100^{100}\)个不同的基础类型的元素。即使算上最大地址的限制,元素的数量也能达到\(10^{18}\)。显然,依次构造每个元素,在空......
  • AT_agc027_f [AGC027F] Grafting 题解
    笑点解析:NOIP模拟赛把这题放在T3。因为每一个点只能动一次,答案一定\(\len\),所以我们分两种情况讨论:当答案小于\(n\)答案如果小于\(n\),那么一定有一个点是一直没有被动过的。我们枚举这个点,将无根树转化为两棵以这个点为根的有根树。我们将第一棵树和第二棵树同构的部分......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\),求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位,注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数,因此无需使用整数输入,直接将输入看成......
  • AtCoder Beginner Contest 258 A~Ex 题解
    D-Trophy题目大意有一个游戏,由\(N\)个关卡组成。第\(i\)个关卡由一个数对\((A_i,B_i)\)组成。要通过一个关卡,你必须先花\(A_i\)的时间看一次介绍。然后,用\(B_i\)的时间打通这个关卡。若想多次通过同一个关卡,则第一次需要看介绍,后面无需再看(即如果想打通第\(i\)关\(N\)次,则所......
  • AtCoder Beginner Contest 260 A~F 题解
    A-AUniqueLetter题目大意给定一个长度为\(3\)的字符串\(S\)。输出\(S\)中出现正好一次的字母(任意,如abc中,三个字母都可为答案)。如果没有,输出-1。数据保证\(S\)的长为\(3\),且由小写英文字母组成。输入格式\(S\)输出格式输出任意符合条件的答案。样例\(S\)输出......
  • LINE Verda Programming Contest (AtCoder Beginner Contest 263) A~E 题解
    A-FullHouse题目大意来自一个掼蛋爱好者的翻译qwq给定一副扑克牌中五张牌的编号\(A,B,C,D,E\),判断这五张是否为一组“三带二”。(不懂的自行百度数据范围:\(1\leA,B,C,D,E\le13\),且\(A,B,C,D,E\)不会全部相同。输入格式\(A~B~C~D~E\)输出格式如果是“三带二”,输出Yes;否......
  • BZOJ 1396 识别子串 题解
    Statement给\(S\),令\(x\)为\(S\)的第\(k\)个字符,称\(T=S[i..j]\)为关于\(x\)的识别子串,当且仅当:\(i\lek\lej\)(含\(x\)这一位)\(T\)在\(S\)中只出现一次求\(S\)关于每一位字符的最短识别子串长度,\(|S|\le10^5\).Solution1以下是我没看题解瞎胡的首先......
  • 动态规划01背包的一个例题——洛谷P2871 题解
    题面有N件物品和一个容量为M的背包。第I件物品的重量是W[i],价值是D[i].求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。样例数据输入46142631227输出23分析(如果亲爱的读者对动态规划略有了解的话应该能看出来这是个01背包的板子......
  • BZOJ 3796 Mushroom追妹纸 题解
    Statement给\(s_1,s_2,s_3\),求最长的\(w\)的长度,满足\(w\)是\(s_1\)子串\(w\)是\(s_2\)子串\(s_3\)不是\(w\)子串Solution1以下是我没看题解瞎胡的首先一个弱智想法是,枚举\(s_1\)上\(w\)的左端点,二分右端点,判定时\(s_2\)用SAM,\(s_3\)用单串AC自动......