题解：CF1616G Just Add an Edge

· · 题解

给定一个 DAG，所有边 u\to v 满足 u<v，求有多少对 (x,y) 使得 x>y 且添加 (x,y) 这条边后的图存在哈密顿路径。

zak 好闪！拜谢 zak！这篇融合多个思路写清楚了一些。

首先特判原图存在哈密顿路的情况，答案为 \frac{n(n-1)}{2}.

否则添加 (x,y) 后，哈密顿路径必定形如：

1\xrightarrow{+1\text{ each time}} {\color{red}y-1\looparrowright x}\to {\color{blue}y\looparrowright x+1}\xrightarrow{+1\text{ each time}}n

其中红蓝部分的两条链不能有交，且并起来是 [y-1,x+1]​。

考察红蓝链长啥样：考虑 y-1 连的是 y-1\to u，那么必定有 y\xrightarrow{+1\text{ each time}}u-1。

然后考虑 u-1 连的是 u-1\to u'，那么必定有：u\xrightarrow{+1\text{ each time}} u'-1。

我们自然就发现规律了，只有形如 (i-1,i) 和 (i,i-1)​ 的点对是有用的。

记 A_{i,0/1} 分别表示点对 (i-1,i),(i,i-1)。我们对这 2n​ 个点对连边：

最终我们需要判断 $A_{y,0}$ 能否到达 $A_{x+1,0}$​。 直接建立 **DAG** 判断可达性，仍然 $\mathcal{O} (n)$ 个点 $\mathcal{O} (m)$ 条边，复杂度 $\mathcal{O} (\frac{nm}{w})$​，有点难过。 - 特别的，为了处理 $1,n$ 处的边界问题，我们在**原图**中新建 $0,n+1$ 两个点。 并**在原图中**添加 $0\to [1,n],[1,n]\to n+1$ 这 $2n$ 条边即可。 [$\text{zak's record}$](https://codeforces.com/contest/1616/submission/141286302) --- 你都转化为 **DAG** 可达性了，自然要看看这个 **DAG** 有没有啥特殊性质。 由于原图不存在哈密顿路，所以一定存在一个 $p$ 满足 $p\to p+1$ 没有边。 根据分析的规律，容易推出一个**重要结论**：任意一条 $A_{y,0}\to A_{x+1,0}$ 的路径**一定经过** $(p, p + 1)$ 或 $(p + 1, p)$​。 > 证明就考虑 $p + 1$ 必定是被 $<p$ 的点跨过来的，自然就是必经点了。 我们先考虑 $(p, p + 1)$​。可以从 $(p, p + 1)$​ 开始，在正图和反图上分别求出它能到达的点。 正/反图上它能到达的点一定在它右/左边，所以从中任意选出一对都是合法的 $(x,y)$​。 对于 $(p + 1, p)$​ 也是类似考虑。 最后我们把两个答案加起来再容斥掉重复部分即可，**注意要扣掉加一条 $(i,i+1)$ 的边使得有哈密顿路的情况**。 时间复杂度 $\mathcal{O}(T(n + m))$​。 [$\bf{record}$](https://codeforces.com/contest/1616/submission/326382114)