「BalticOI 2020」病毒

设点集大小为$N$，边集总长度$\sum k=M$，模板串总长$L=\sum ℓ$

涉及到多串匹配的转移问题，容易想到$\text{AC}$自动机

因为本题状态非常少，可以暴力矩阵维护转移，暴力计算由状态$i$转移至状态$j$，且中途不匹配的最小长度

有$NL^2$个状态

给定的是一张有向图，可以用奇怪的$\text{Bellman-Ford,Dijkstra}$完成暴力转移

复杂度未知。。。上界应该比较高，但是鉴于常数小可以通过

优化的转移：把每一条边的前缀拆出来，建立虚点

这样以来，所有状态转移可以归纳为 虚点+实点 $\to$ 虚点/实点

一共有$(N+M)L^2$个状态，$(N+M)L^2$种转移，每种转移涉及两个元素，产生$L$个元素

故对于每种转移的每一方，被遍历时都要枚举依次转移，共有$2(N+M)L^3$次转移

因此可以认为建立的图有$(N+M)L^2$个点，$2(N+M)L^3$条边

对此运行 类似 最短路算法即可

因此用$\text{Dijkstra}$维护转移的复杂度为$O(\ (N+M)L^3\ \log ((N+M)L^2)\ )$

—-以下是未优化Bellman-Ford代码——

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
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=110,M=54;


int n,m,k;
typedef vector <int> V;
int trie[M][2],fail[M],mk[M],cnt;
void Ins(const V &S){
	int now=0;
	for(int i:S) {
		int &nxt=trie[now][i];
		if(!nxt) nxt=++cnt;
		now=nxt;
	}
	mk[now]=1;
}
void Build(){
	static queue <int> que;
	rep(i,0,1) if(trie[0][i]) que.push(trie[0][i]);
	while(!que.empty()) { 
		int u=que.front(); que.pop();
		mk[u]|=mk[fail[u]];
		rep(i,0,1){
			int &v=trie[u][i];
			if(v) que.push(v);
			(!v?v:fail[v])=trie[fail[u]][i];
		}
	}
    // delete illegal state
	rep(i,0,cnt) rep(j,0,1) if(mk[trie[i][j]]) trie[i][j]=cnt+1;
}

V Read(){
	V Res;
	rep(i,1,rd()) Res.pb(rd());
	return Res;
}

vector <V> G[N];
int E[N][N];
const ll INF=-1;
ll dis[N][M][M],ans[N];
int fl=1;
void Work(int u){
	static ll F[M][M],G[M][M];
	ll f=INF;
	for(V S:(::G[u])) {
		memset(F,255,sizeof F);
		rep(i,0,cnt) F[i][i]=0;
		for(int c:S) {
			rep(i,0,cnt) rep(j,0,cnt) G[i][j]=F[i][j],F[i][j]=INF;
			rep(i,0,cnt) rep(j,0,cnt) if(G[i][j]<INF) 
				rep(k,0,cnt) if(G[i][j]+dis[c][j][k]>=max(G[i][j],dis[c][j][k])) 
					cmin(F[i][k],G[i][j]+dis[c][j][k]);
		}
		rep(i,0,cnt) rep(j,0,cnt) if(dis[u][i][j]>F[i][j]) dis[u][i][j]=F[i][j],cmin(f,F[i][j]);
	}
	if(f!=INF) fl=1;
}

int main(){
	n=rd()-1,m=rd(),k=rd();
	rep(i,1,m) {
		int u=rd(); V w=Read();
		G[u].pb(w);
		for(int v:w) E[v][u]=1;
	}
	rep(i,1,k) Ins(Read());
	Build();
	memset(dis,255,sizeof dis),memset(ans,255,sizeof ans);
	rep(u,0,1) rep(i,0,cnt) if(!mk[i]) dis[u][i][trie[i][u]]=1;
	while(fl){
		fl=0;
		rep(i,2,n) Work(i);
	}
	rep(i,2,n) rep(j,0,cnt) if(!mk[j]) cmin(ans[i],dis[i][0][j]);
	rep(i,2,n) {
		if(ans[i]==INF) puts("YES");
		else printf("NO %llu\n",ans[i]);
	}
}

——以下是无比垃圾的优化代码——

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define pb push_back
typedef pair <int,int> Pii;
#define mp make_pair
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=210,M=52;
const ll INF=-1;

int n,m,k,c;
typedef vector <int> V;
int trie[M][2],fail[M],mk[M],cnt;
void Ins(const V &S){
	int now=0;
	for(int i:S) {
		int &nxt=trie[now][i];
		if(!nxt) nxt=++cnt;
		now=nxt;
	}
	mk[now]=1;
}
void Build(){
	static queue <int> que;
	rep(i,0,1) if(trie[0][i]) que.push(trie[0][i]);
	while(!que.empty()) { 
		int u=que.front(); que.pop();
		mk[u]|=mk[fail[u]];
		rep(i,0,1){
			int &v=trie[u][i];
			if(v) que.push(v);
			(!v?v:fail[v])=trie[fail[u]][i];
		}
	}
	mk[cnt+1]=1;
	rep(i,0,cnt) rep(j,0,1) if(mk[i] || mk[trie[i][j]]) trie[i][j]=cnt+1;
}

V Read(){
	V Res;
	rep(i,1,rd()) Res.pb(rd());
	return Res;
}

vector <Pii> G[N];
ll dis[N][M][M];
struct Node{
	int u,s,t;
	ll d;
	bool operator < (const Node &__) const {
		return d>__.d;
	}
};
priority_queue <Node> que;
void Upd(int u,int s,int t,ll d){
	if(mk[s]||mk[t]||dis[u][s][t]<=d) return;
	dis[u][s][t]=d,que.push((Node){u,s,t,d});
}

int main(){
	c=n=rd()-1,m=rd(),k=rd();
	++c; // 建立一个空虚点
	rep(i,1,m) {
		int u=rd(); V w=Read();
		int lst=n+1;
		rep(j,0,w.size()-1) {
			if(j==jend) G[lst].pb(mp(w[j],u)),G[w[j]].pb(mp(lst,u));
			else G[lst].pb(mp(w[j],++c)),G[w[j]].pb(mp(lst,c)),lst=c;
		}
	}
	rep(i,1,k) Ins(Read());
	Build();
	memset(dis,255,sizeof dis);
	rep(i,0,cnt) if(!mk[i]) dis[n+1][i][i]=0; // 单位矩阵
	rep(u,0,1) rep(i,0,cnt) Upd(u,i,trie[i][u],1);
	while(!que.empty()) {
		int u=que.top().u,s=que.top().s,t=que.top().t;
		ll d=que.top().d;  que.pop();
		if(d>dis[u][s][t]) continue;
		for(auto i:G[u]) {
			int v=i.first,to=i.second;
			if(u<=n) {
				rep(i,0,cnt) if(dis[v][i][s]<INF) Upd(to,i,t,dis[v][i][s]+d);
			} else {
				rep(i,0,cnt) if(dis[v][t][i]<INF) Upd(to,s,i,d+dis[v][t][i]);
			}
		}
	}
	rep(i,2,n) {
		ll ans=-1;
		rep(j,0,cnt) if(!mk[j]) ans=min(ans,dis[i][0][j]);
		if(ans==INF) puts("YES");
		else printf("NO %llu\n",ans);
	}
}