妙妙图论题。
*3500 的牛逼题。
如果原图已有哈密顿回路，那么一定是 $1\to 2\to \dots \to n$，这种情况下的答案为 $\binom{n}{2}$。
考虑更一般的情况，发现添加返祖边 $(v,u)$ 的哈密顿回路一定形如：
这是因为在经过之后 $u-1$ 之后是不能回到 $<u$ 的点的。问题转化为，找到不交的 $1\to v$ 与 $u\to n$ ，并且两条路径覆盖 ${1,\dots, n}$。
我们新建 $0,n+1$ 两个点，并分别 $0$ 向所有点连边，所有点向 $n+1$ 连边，这样回路的起点与终点就固定了， 方便计算。
考虑暴力做法，考虑枚举 $u$ 然后进行 DP，设 $f_{x,0/1}$ 表示当前点分别在两条链上是否有合法方案。只考虑，前一个点与当前点所在的不同即可。得到 $\mathcal O(n^2)$ 做法。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int N=1.5e5+10,M=1.5e5+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n,m;
int l,r;
int pre[N],suf[N];
bool f[N][2];
bool flag[N];
vector<int>rev[M];
inline void add(int u,int v)
{
rev[v].push_back(u);
}
inline void solve()
{
memset(flag,0,sizeof(flag));
memset(f,0,sizeof(f));
read(n,m);
for(int i=0;i<=n+1;i++)rev[i].clear();
for(int i=2;i<=n;i++)add(0,i);
for(int i=1;i<n;i++)add(i,n+1);
for(int i=1;i<=m;i++)
{
int u,v;
read(u,v);
if(u+1==v)flag[v]=1;
else add(u,v);
}
flag[1]=flag[n+1]=1;
pre[0]=0,suf[n+1]=n+1;
for(int i=1;i<=n+1;i++)pre[i]=flag[i]?pre[i-1]:i;
for(int i=n;~i;i--)suf[i]=flag[i+1]?suf[i+1]:i;
if(!pre[n+1])
{
printf("%lld\n",1ll*n*(n-1)/2);
return ;
}
ll ans=0;
for(int i=1;i<=suf[0]+1;i++)
{
memset(f,0,sizeof(f));
f[i][1]=1;
for(int j=i+1;j<=n+1;j++)
for(int v:rev[j])
{
for(int t=0;t<2;t++)
f[j][t]|=((suf[v+1]>=j-1)&f[v+1][t^1]);
}
for(int j=pre[n+1];j<=n+1;j++)
ans+=f[j][1];
}
if(suf[0]+1==pre[n+1])ans--;
printf("%lld\n",ans);
}
int main()
{
read(T);
while(T--)solve();
return 0;
}
|
注意到关键性质，如果原图没有哈密顿回路的话，一定存在一个最小的 $p$，满足 $p$ 未向 $p+1$ 连边，于是 $p+1$ 将哈密顿回路分割成两部分 $[0,p+1],[p+2,n+1]$。转移的过程中不会跨过 $p+1$，所以这两个部分是相互独立的。于是我们可以分开计算，再将两段合并即可。但是注意到可能会出现 $f_{u,0}=f_{u,1}=f_{v,0}=f_{v,1}=1$ ，按照上述计算方式会被算两次，但实际上只存在一种连边方式，对于这一部分注意减掉就好了。
似乎比较好写但是还是要注意很多细节。具体也可以看看代码：
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int N=1.5e5+10,M=1.5e5+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int T,n,m;
int p,q;
int pre[N],suf[N];
bool f[N][2];
bool flag[N];
vector<int>rev[M];
inline void add(int u,int v)
{
rev[v].push_back(u);
}
inline void solve()
{
memset(flag,0,sizeof(flag));
memset(f,0,sizeof(f));
read(n,m);
for(int i=0;i<=n+1;i++)rev[i].clear();
for(int i=2;i<=n;i++)add(0,i);
for(int i=1;i<n;i++)add(i,n+1);
for(int i=1;i<=m;i++)
{
int u,v;
read(u,v);
if(u+1==v)flag[v]=1;
else add(u,v);
}
flag[1]=flag[n+1]=1;
pre[0]=0,suf[n+1]=n+1;
for(int i=1;i<=n+1;i++)pre[i]=flag[i]?pre[i-1]:i;
for(int i=n;~i;i--)suf[i]=flag[i+1]?suf[i+1]:i;
if(!pre[n+1])
{
printf("%lld\n",1ll*n*(n-1)/2);
return ;
}
p=suf[0],q=pre[n+1];
ll ans=0;
f[p+1][1]=1;
for(int i=p+1;i<=n+1;i++)
for(int v:rev[i])
for(int t=0;t<2;t++)c4
f[i][t]|=((suf[v+1]>=i-1)&f[v+1][t^1]);
for(int i=p+1;~i;i--)
for(int v:rev[i])
for(int t=0;t<2;t++)
f[v+1][t]|=((suf[v+1]>=i-1)&f[i][t^1]);
int lcnt,rcnt;
for(int t=0;t<2;t++)
{
lcnt=0,rcnt=0;
for(int i=0;i<=p+1;i++)lcnt+=f[i][t];
for(int i=q;i<=n+1;i++)rcnt+=f[i][t];
ans+=1ll*lcnt*rcnt;
}
lcnt=0,rcnt=0;
for(int i=0;i<=p;i++)lcnt+=f[i][0]&f[i][1];
for(int i=q;i<=n+1;i++)rcnt+=f[i][0]&f[i][1];
ans-=1ll*lcnt*rcnt;
if(p+1==q)ans--;
printf("%lld\n",ans);
}
int main()
{
read(T);
while(T--)solve();
return 0;
}
|