隐藏
「SDOI2017」天才黑客 - 点集转化+虚树+线段树优化建边+最短路 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

「SDOI2017」天才黑客 - 点集转化+虚树+线段树优化建边+最短路

发表于 更新于 分类于 Valine：

题目大意

    SD0062 号选手小 Q 同学为了偷到 SDOI7012 的试题，利用高超的黑客技术潜入了 SDOI 出题组的内联网的中央控制系统，然而这个内联网除了配备有中央控制系统，还为内联网中的每条单向网线设定了特殊的通信口令，这里通信口令是一个字符串，不同网线的口令可能不同。这让小 Q 同学感觉有些棘手， 不过这根本难不倒他，很快他就分析出了整个内联网的结构。

    内联网中有$n$个节点（从$1$到$n$标号）和$m$条单向网线，中央控制系统在第$1$个节点上，每条网线单向连接内联网中的某两个节点，从$1$号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序，应用程序会携带一条通信口令，当且仅当程序的口令与网线的口令相同时，程序才能通过这条网线到达另一端的节点继续运行，并且通过每条网线都需要花费一定的时间。

    每个应用程序可以在任意一个节点修改通信口令，修改通信口令花费的时间可以忽略不计，但是为了减小修改量，需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀（记其长度为$\text{len}$），由于获取网线的口令的某个字符会比较耗时，调用一次这个子程序需要花费$\text{len}$个单位时间。

    除此之外，小 Q 同学还在中央控制系统中发现了一个字典，每条网线的口令都是字典中的某个字符串。具体来说，这个字典是一棵$k$个节点（从$1$到$k$标号）的有根树，其中根是第$1$个节点，每条边上有一个字符，字符串$S$在字典中当且仅当存在某个点$u$使得从根节点出发往下走到$u$的这条路径上的字符顺次拼接构成$S$。

    现在小 Q 同学在$1$号节点同时开启了$n-1$个应用程序，这些应用程序同时运行且互不干扰，每个程序的通信口令都为空，他希望用最短的时间把这些程序分别发送到其他节点上，你需要帮小 Q 同学分别计算出发送到第$i(=2,3,\ldots,n)$个节点的程序完成任务的最短时间。

题目分析

很毒瘤的一道题。

第一步比较好想，先将图进行转化。
将边集转成点集，并将原边拆成两个点，两个点之间连边（原边权）。
然后重新建立边集，对于每个原图的点而言，复杂度为$O(deg^2)$，轻松被卡。

考虑对于每一个原图的点，先找出该点所连接的边在trie树上的位置，构建出虚树。
考虑对其边权相同的边一起新建。
枚举lcp，即在trie树上枚举lca，因此对于$lca$为枚举的点的点对，其边权均为lca的深度$-1$。
那么我们可以使用线段树来优化建边，将建边复杂度降到$O(n\log n)$级别。

重建好了图，就可以跑最短路了。

Claris似乎有种实现起来更简单的方法，然而我不会。

代码

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=50005,maxm=50005,maxk=20005,K=15,N=2000005;

struct Edge {
	int from,to,dist,pos;
} edges[maxm];

vector<int> In[maxn],Out[maxn],trie[maxn];
int n,m,k,step=0,cnt=0,Depth[maxk],First[maxk],Last[maxk],p[maxk][K];
LL Dist[maxn];

void AddEdge(int x,int y) {
	trie[x].push_back(y);
}

void Dfs(int Now,int fa,int depth) {
	Depth[Now]=depth;
	First[Now]=++step;
	p[Now][0]=fa;
	for(int i=1; i<K; i++)
		if(~p[Now][i-1])p[Now][i]=p[p[Now][i-1]][i-1];
		else break;
	for(int Next:trie[Now]) {
		if(Next==fa)continue;
		Dfs(Next,Now,depth+1);
	}
	Last[Now]=step;
}

int LCA(int a,int b) {
	if(Depth[a]<Depth[b])swap(a,b);
	for(int i=K-1; i>=0; i--)
		if(Depth[a]==Depth[b])break;
		else if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
	if(a==b)return a;
	for(int i=K-1; i>=0; i--)
		if(~p[a][i]&&p[a][i]!=p[b][i]) {
			a=p[a][i];
			b=p[b][i];
		}
	return p[a][0];
}

struct Graph {
	vector<Edge> edges[N];
	void AddEdge(int x,int y,int v) {
		edges[x].push_back((Edge) {x,y,v});
	}
	void clear(int n) {
		for(int i=1; i<=n; i++)edges[i].clear();
	}
#define pii pair<LL,int>
#define mp make_pair
	LL dist[N];
	bool vst[N];
	void dijkstra(int n) {
		priority_queue<pii,vector<pii>,greater<pii> > Q;
		for(int i=1; i<=n; i++)dist[i]=LLONG_MAX/2,vst[i]=0;
		for(int x:Out[1]) {
			dist[x]=0;
			Q.push(mp(0,x));
		}
		while(!Q.empty()) {
			int Now=Q.top().second;
			Q.pop();
			if(vst[Now])continue;
			vst[Now]=1;
			for(Edge& e:edges[Now]) {
				int Next=e.to;
				if(dist[Next]>dist[Now]+e.dist) {
					dist[Next]=dist[Now]+e.dist;
					Q.push(mp(dist[Next],Next));
				}
			}
		}
		clear(n);
	}
} newG;

struct Virtual_Tree {
	vector<int> vtree[N];
	int First[N],Last[N],M[N],step,uroot,droot,upos[N],dpos[N];
	void AddEdge(int x,int y) {
		vtree[x].push_back(y);
	}
	void dfs(int Now) {
		First[Now]=++step;
		M[step]=Now;
		for(int Next:vtree[Now])dfs(Next);
		Last[Now]=step;
	}
	void clear(int Now) {
		for(int Next:vtree[Now])clear(Next);
		vtree[Now].clear();
	}
	struct Tree {
		int ls,rs,left,right;
		Tree(int l=0,int r=0):left(l),right(r),ls(0),rs(0) {}
	} tree[N];
	void build(int &index,int Left,int Right,bool down) {
		index=++cnt;
		tree[index]=Tree(Left,Right);
		if(Left==Right) {
			if(!down)upos[Left]=index;
			else dpos[Left]=index;
			return;
		}
		int mid=(Left+Right)>>1;
		build(tree[index].ls,Left,mid,down);
		build(tree[index].rs,mid+1,Right,down);
		if(!down) {
			newG.AddEdge(index,tree[index].ls,0);
			newG.AddEdge(index,tree[index].rs,0);
		} else {
			newG.AddEdge(tree[index].ls,index,0);
			newG.AddEdge(tree[index].rs,index,0);
		}
	}
	void link(int index,int Left,int Right,int pos,bool down) {
		if(Right<tree[index].left||Left>tree[index].right)return;
		if(Left<=tree[index].left&&Right>=tree[index].right) {
			if(!down)newG.AddEdge(pos,index,0);
			else newG.AddEdge(index,pos,0);
			return;
		}
		link(tree[index].ls,Left,Right,pos,down);
		link(tree[index].rs,Left,Right,pos,down);
	}
	void Link(int L1,int R1,int L2,int R2,int v) {
		if(L1>R1||L2>R2)return;
		link(droot,L1,R1,cnt+1,1);
		link(uroot,L2,R2,cnt+2,0);
		newG.AddEdge(cnt+1,cnt+2,v);
		cnt+=2;
	}
	void work(int root,int Now) {
		dfs(root);
		build(uroot,1,step,0),build(droot,1,step,1);
		for(int x:In[Now])newG.AddEdge(m+x,dpos[First[edges[x].pos]],0);
		for(int x:Out[Now])newG.AddEdge(upos[First[edges[x].pos]],x,0);
		for(int i=1; i<=step; i++) {
			int x=M[i];
			Link(First[x],First[x],First[x],Last[x],Depth[x]-1);
			for(int y:vtree[x]) {
				Link(First[y],Last[y],First[x],First[y]-1,Depth[x]-1);
				Link(First[y],Last[y],Last[y]+1,Last[x],Depth[x]-1);
			}
		}
		clear(root);
		step=0;
	}
} vt;

bool cmp(int x,int y) {
	return First[x]<First[y];
}

vector<int> a;
int root;

void Build(int x) {
	a.clear();
	for(int y:In[x])a.push_back(edges[y].pos);
	for(int y:Out[x])a.push_back(edges[y].pos);
	sort(a.begin(),a.end(),cmp);
	int tmp=a.size();
	for(int i=0; i<tmp-1; i++)a.push_back(LCA(a[i],a[i+1]));
	sort(a.begin(),a.end(),cmp);
	auto it=unique(a.begin(),a.end());
	a.erase(it,a.end());
	static int top=0,S[N];
	root=S[++top]=a[0];
	for(int i=1; i<a.size(); i++) {
		int now=a[i];
		while(top>=1) {
			if(First[now]>=First[S[top]]&&First[now]<=Last[S[top]]) {
				vt.AddEdge(S[top],now);
				break;
			}
			top--;
		}
		if(S[top]!=now)S[++top]=now;
	}
	vt.work(root,x);
}

void Clear() {
	for(int i=1; i<=k; i++)trie[i].clear();
	for(int i=1; i<=n; i++)In[i].clear(),Out[i].clear();
	memset(p,-1,sizeof(p));
	step=0;
}

int main() {
	int t=Get_Int();
	while(t--) {
		Clear();
		n=Get_Int();
		m=Get_Int();
		k=Get_Int();
		for(int i=1; i<=m; i++) {
			edges[i].from=Get_Int();
			edges[i].to=Get_Int();
			edges[i].dist=Get_Int();
			edges[i].pos=Get_Int();
			In[edges[i].to].push_back(i);
			Out[edges[i].from].push_back(i);
		}
		for(int i=1; i<k; i++) {
			int x=Get_Int(),y=Get_Int(),v=Get_Int();
			AddEdge(x,y);
		}
		Dfs(1,0,1);
		for(int i=1; i<=m; i++)newG.AddEdge(i,m+i,edges[i].dist);
		cnt=m<<1;
		for(int i=1; i<=n; i++)if(In[i].size()&&Out[i].size())Build(i);
		newG.dijkstra(cnt);
		for(int i=1; i<=n; i++)Dist[i]=LLONG_MAX/2;
		for(int i=1; i<=m; i++)Dist[edges[i].to]=min(Dist[edges[i].to],newG.dist[m+i]);
		for(int i=2; i<=n; i++)printf("%lld\n",Dist[i]);
	}
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~