题意
给定一张 \(\rm DAG\),\(\rm DAG\) 中的边都形如 \(i \to j (i < j)\)。要求在 \(\rm DAG\) 中添加边 \(x \to y (x > y)\) 的二元组 \((x,y)\) 个数,满足添加完边后存在一条哈密顿路径。\(t\) 组数据。
数据范围:\(1 \le t \le 5\),\(1 \le n,m \le 1.5 \times 10^5\)。
题解
首先特判掉本身存在哈密顿路径的情况。
否则我们就要利用到我们添加的边 \(x \to y\)。容易发现新图存在哈密顿路径,等价于在原图存在一条终点为 \(x\) 和起点为 \(y\) 的不相交路径,使得两条路径不交地覆盖 \(\{1,...,n\}\)。
为了方便处理,添加点 \(0\) 和 \(n+1\),\(0\) 在终点为 \(x\) 的路径中,\(n+1\) 在起点为 \(y\) 的路径中。
我们把终点为 \(x\) 的路径上的点涂上 0
,起点为 \(y\) 的路径涂上 1
。这样就形成了一个 01
串 \(s\)。
容易发现 \(s_{0},...,s_{y-1}\) 都是 0
,\(s_{x+1},...,s_{n+1}\) 都是 1
。
考虑固定了 \(y\) 怎么做。
我们只关心 \(s_{i} \neq s_{i + 1}\) 的情况。设 \(dp_{i,w}\) 表示是否有可能满足 \(s_{i - 1} = w, s_{i} = w \oplus 1\)。转移是 trivial 的。这是暴力代码。时间复杂度 \(\Theta(nm)\)。
考虑优化。设 \(l\) 为第一个 \(i\) 满足 \(i\) 没有向 \(i + 1\) 连边。那么有 \(s_{l} \neq s_{l + 1}\)。
所以 \(dp_{l+1}\) 是我们 \(\rm DP\) 状态的必经之路。我们可以以 \(l+1\) 为分界线,对 \([0, l+1]\) 和 \([l+1,n+1]\) 分别 \(dp\),其 \(dp\) 的值可以表示成只和 \(dp_{l+1}\) 有关的形式。然后合并两边的信息即可。
代码
需要特判可以加一条 \(x < y\) 并形成哈密顿路径的情况。
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define sz(a) ((int) a.size())
#define vi vector<int>
#define ll long long
#define me(f, x) memset(f, x, sizeof(f))
using namespace std;
const int N = 2e5 + 7;
int n, m, su[N], sv[N];
int pl, pr, nxt[N];
int dp[N][2]; // 01; 10
bool ok[N];
int cnt[4], dnt[4];
vi re[N];
void Main () {
me(ok, 0);
cin >> n >> m;
L(i, 2, n) re[i].clear (), re[i].push_back(0);
re[n + 1].clear ();
L(i, 1, n - 1) re[n + 1].push_back(i);
L(i, 1, m) {
cin >> su[i] >> sv[i];
if(sv[i] == su[i] + 1)
ok[su[i]] = true;
else
re[sv[i]].push_back(su[i]);
}
L(i, 1, n - 1) if(!ok[i]) pr = i + 1;
R(i, n, 1) if(!ok[i]) pl = i;
R(i, n, 1)
nxt[i] = ok[i] ? nxt[i + 1] : i;
if(pl == n)
return cout << (ll) n * (n - 1) / 2 << '\n', void ();
me (dp, 0);
dp[pl + 1][0] = 1;
dp[pl + 1][1] = 2;
L(j, pl + 2, n + 1)
for (const int &t : re[j])
L(o, 0, 1) if(nxt[t + 1] >= j - 1)
dp[j][o] |= dp[t + 1][o ^ 1];
R(j, pl + 1, 1)
for (const int &t : re[j])
L(o, 0, 1) if(nxt[t + 1] >= j - 1)
dp[t + 1][o ^ 1] |= dp[j][o];
me(cnt, 0), me(dnt, 0);
L(i, pr, n + 1)
cnt[dp[i][0]] += 1;
L(i, 1, pl + 1)
dnt[dp[i][0]] += 1;
ll ns = 0;
L(i, 0, 3)
L(j, 0, 3)
if(i & j)
ns += (ll) cnt[i] * dnt[j];
if(pl + 1 == pr)
ns -= 1;
cout << ns << '\n';
}
int main() {
ios :: sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int T;
cin >> T;
while (T--) Main ();
return 0;
}
祝大家学习愉快!