题意
给 张图，每张图有 个结点与若干条普通边（有向）的图，图与图之间相同编号的结点之间有一条从编号较小到编号较大的特殊边，定义一条路径为从编号最小的图的点 出发到达编号最大的图的点 且不能连续经过两条普通边（允许连续经过特殊边），问 张图的一个最大的连续子段使得其不同路径数目小于 。
思路
首先对于 的 DP 还是比较好想的，我们直接枚举这个子段，然后设 表示从这个子段的开始走到末尾的点 的路径数。
然后考虑进行优化，由于题目中说了只需要路径数小于等于 而不一定要走到，所以我们的子段越长一定是越难合法的。
那么我们考虑进行双指针，但是一般的双指针尺取需要删除操作，显然我们不能支持删除。
那么 是不太可能了，我们发现 很小而 很大，可以考虑使用 的复杂度来换 的复杂度。
由于一维的距离是难以进行操作（只支持在后端加边），所以我们使用邻接矩阵来表示这个数组。
这样在两个方向上的加点（话说，我们好像是加一整张图来着）就可以做到了，由于图非常的稀疏，通过先枚举较为稀疏的矩阵可以将加入单点的操作的时间复杂度降为 。
但是还是不能删除。
那么我们掏出无删尺取（Baka's Trick），并且发现我们合并的时间复杂度实际上是 。
因为我们合并操作其实只关心 ，而只得到这个值的复杂度是很小的。
那么最后的时间复杂度就是 。
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
| #include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using ll=long long;
using namespace std;
const int N=5010,FSIZE=1<<26;
int n,m,k;
struct graph{
ll a[21][21];
graph(){memset(a,0,sizeof(a));}
void clear(){memset(a,0,sizeof(a));}
ll operator()()const{return(a[1][m]);}
}g[N],f[N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
bool f=1;
for(;48>*InF||*InF>57;f^=*InF++=='-');
for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
x=f?x:-x;
}
graph pushL(const graph &a,const graph &b){
graph re=a;
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
re.a[i][j]+=b.a[i][j];
for(int k=1;k<=m;++k)
for(int i=1;i<=m;++i)
if(a.a[i][k])
for(int j=1;j<=m;++j)
re.a[i][j]+=a.a[i][k]*b.a[k][j];
return(re);
}
graph pushR(const graph &a,const graph &b){
graph re=a;
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
re.a[i][j]+=b.a[i][j];
for(int k=1;k<=m;++k)
for(int j=1;j<=m;++j)
if(b.a[k][j])
for(int i=1;i<=m;++i)
re.a[i][j]+=a.a[i][k]*b.a[k][j];
return(re);
}
ll merge(const graph &a,const graph &b){
ll re=a()+b();
for(int i=1;i<=m;++i)
re+=a.a[1][i]*b.a[i][m];
return(re);
}
void work(){
int ans=0;
read(n);read(m);read(k);
for(int i=1,l;i<=n;++i){
read(l);
g[i].clear();
for(int j=1,x,y;j<=l;++j){
read(x);read(y);
g[i].a[x][y]=1;
}
}
f[1]=g[1];
for(int l=1,mid=1,r=1;1;f[r]=g[r]){
for(;l>1&&(f[l-1]=pushL(g[l-1],f[l]))()<=k;--l);
for(;l<=mid;++l){
for(;r<n&&merge(f[l],(f[r+1]=pushR(r>mid?f[r]:f[0],g[r+1])))<=k;++r);
for(;merge(f[l],f[r])>k&&l<=mid;++l);
ans=max(ans,r-l+1);
}
if(l>n) break;
l=mid=r;
}
printf("%d\n",ans);
}
int main(){
fread(BuF,1,FSIZE,stdin);
int t;
for(read(t);t--;work());
fclose(stdin);
fclose(stdout);
return(0);
}
|