文档章节

[SDOI2017]天才黑客[最短路、前缀优化建图]

o
 osc_fmg49rzg
发布于 2019/03/20 11:30
字数 1206
阅读 17
收藏 0
lcp

精选30+云产品,助力企业轻松上云!>>>

题意

一个 $n$ 点 $m$ 边的有向图,还有一棵 $k$ 个节点的 trie ,每条边上有一个字符串,可以用 trie 的根到某个节点的路径来表示。每经过一条边,当前携带的字符串就会变成边上的字符串,经过一条边的代价是边权+边上的字符串和当前字符串的 lcp,问从 1 号点走到所有点的最小代价。

$n,m\le 50000, k\le 20000$

分析

  • 将边看成点,如果有 $e1 \rightarrow x\rightarrow e2$ , 连边 $e1 \rightarrow e2$ ,代价就是 lcp ,考虑优化建图。
  • 实际本题的字典树是一个提示,可以将一个点的子节点按照字符大小遍历,根据后缀数组求 $height$ 的性质容易知道两个点 $u,v$ 的 lca 就是他们 dfs 序中间的所有相邻点的 lca 的深度最小的那一个
  • 这个结论也可以通过点作为 lca 的依据(至少两个子树内有关键点)得到,也就是说一定可以通过这种方式表示出这两个点的lca。所以前缀后缀优化建图即可。
  • 复杂度 $O(nlogn)$ 。
  • 注意可能出现一条出边一条入边的字符串相同的情况,所以每个前缀节点还要直接连向对应的后缀节点。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
    int x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
    return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 5e5 + 7, inf = 0x7fffffff;
int n, m, ndc, edc, T, k;
int a[N], b[N], c[N], d[N];
vector<int> A[N], B[N];
struct edge {
	int lst, to, c;
	edge(){}edge(int lst, int to, int c):lst(lst), to(to), c(c){}
};
namespace Trie {
	edge e[N];
	int edc, tim, pc;
	int head[N], in[N], pos[N], mi[N][20], dep[N], Log[N];
	void Add(int a, int b) {
		e[++edc] = edge(head[a], b, 0), head[a] = edc;
	}
	void dfs(int u) {
		mi[pos[u] = ++pc][0] = u;
		in[u] = ++tim;
		go(u) {
			dep[v] = dep[u] + 1;
			dfs(v);
			mi[++pc][0] = u;
		}
	}
	void rmq_init() {
		Log[1] = 0;
		for(int i = 2; i <= pc; ++i) Log[i] = Log[i >> 1] + 1;
		for(int k = 1; 1 << k <= pc; ++k)
		for(int i = 1; i + (1 << k) - 1 <= pc; ++i)
		mi[i][k] = in[mi[i][k - 1]] < in[mi[i + (1 << k - 1)][k - 1]] ? mi[i][k - 1] : mi[i + (1 << k - 1)][k - 1];
	}
	int dLca(int l, int r) {
		if(l == r) return dep[l];
		l = pos[l], r = pos[r];
		if(l > r) swap(l, r);
		int k = Log[r - l + 1];
		return in[mi[l][k]] < in[mi[r - (1 << k) + 1][k]] ? dep[mi[l][k]] : dep[mi[r - (1 << k) + 1][k]];
	}
}
bool cmp(int a, int b) {
	return Trie::in[a] < Trie::in[b];
}
int vt[N], head[N], st, ed, vc;
int pre1[N], pre2[N], suf1[N], suf2[N];
edge e[N * 20];
struct Heap {
	int u, dis;
	Heap(){}Heap(int u, int dis):u(u), dis(dis){}
	bool operator <(const Heap &rhs) const {
		return rhs.dis < dis;
	}
};
priority_queue<Heap>Q;
int dis[N], vis[N], ans[N], from[N];
void dijk() {
	fill(dis, dis + ndc + 1, inf);
	fill(vis, vis + ndc + 1, 0);
	dis[st] = 0;
	Q.push(Heap(st, 0));
	while(!Q.empty()) {
		int u = Q.top().u; Q.pop();
		if(vis[u]) continue;vis[u] = 1;
		go(u)if(Min(dis[v], dis[u] + e[i].c + c[v])) {
			Q.push(Heap(v, dis[v]));
			from[v] = u;
		}
	}
	fill(ans, ans + ndc + 1, inf);
	for(int i = 1; i <= m; ++i) Min(ans[b[i]], dis[i]);
	rep(i, 2, n) printf("%d\n", ans[i]);
}
void Add(int a, int b, int c) {
	e[++edc] = edge(head[a], b, c), head[a] = edc;
}
void prepare(int u) {
	vc = 0;
	for(auto v:A[u]) vt[++vc] = d[v];
	for(auto v:B[u]) vt[++vc] = d[v];
	sort(vt + 1, vt + 1 + vc, cmp);
	vc = unique(vt + 1, vt + 1 + vc) - vt - 1;
	rep(i, 1, vc) pre1[i] = ++ndc;
	rep(i, 1, vc) pre2[i] = ++ndc, Add(pre1[i], pre2[i], Trie::dep[vt[i]]);
	rep(i, 1, vc) suf1[i] = ++ndc;
	rep(i, 1, vc) suf2[i] = ++ndc, Add(suf1[i], suf2[i], Trie::dep[vt[i]]);
	for(auto v:A[u]) {
		int p = lower_bound(vt + 1, vt + 1 + vc, d[v], cmp) - vt;
		Add(v, pre1[p], 0);
		Add(v, suf1[p], 0);
	}
	for(auto v:B[u]) {
		int p = lower_bound(vt + 1, vt + 1 + vc, d[v], cmp) - vt;
		Add(pre2[p], v, 0);
		Add(suf2[p], v, 0);
	}
	rep(i, 1, vc - 1) {
		Add(pre1[i], pre1[i + 1], 0);
		Add(pre2[i], pre2[i + 1], 0);
		Add(pre1[i], pre2[i + 1], Trie::dLca(vt[i], vt[i + 1]));
	}
	for(int i = vc; i >= 2; --i) {
		Add(suf1[i], suf1[i - 1], 0);
		Add(suf2[i], suf2[i - 1], 0);
		Add(suf1[i], suf2[i - 1], Trie::dLca(vt[i], vt[i - 1]));
	}
}
int main() {
	T = gi();
	while(T--) {
		n = gi(), m = gi(), k = gi();
		ndc = m;
		Trie::edc = edc = 0;
		Trie::tim = Trie::pc = 0;
		fill(Trie::head, Trie::head + k + 1, 0);
		re(head);
		rep(i, 1, n) A[i].clear(), B[i].clear();
		
		rep(i, 1, m) {
			a[i] = gi(), b[i] = gi(), c[i] = gi(), d[i] = gi();
			A[b[i]].pb(i);
			B[a[i]].pb(i);
		}
		rep(i, 1, k - 1) {
			int u = gi(), v = gi(), w = gi();
			Trie::Add(u, v);
		}
		Trie::dfs(1);
		Trie::rmq_init();
		rep(i, 1, n) prepare(i);
		st = ++ndc;
		for(auto v:B[1]) Add(st, v, 0);
		dijk();
		fill(c, c + ndc + 1, 0);
	}
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

PO模式你会吗?自动化测试PO模式分层如何实现?

一、什么是PO模式 全称:page object model 简称:POM/PO PO模式最核心的思想是分层,实现松耦合!实现脚本重复使用,实现脚本易维护性! 主要分三层: 1.基础层BasePage:封装一些最基础的s...

osc_s4e6jr85
15分钟前
5
0
lodash compact & concat

前置 本篇随笔包含 _.compact 和 _.concat 及其依赖的工具函数。 你可能需要一些 JavaScript 基础知识才能看懂一些没有注释的细节。 compact _.compact(array) 创建一个新数组,包含原数组中...

osc_xu7n68ts
15分钟前
3
0
Django快速开发实践:Drf框架和xadmin配置指北

步骤 既然是快速开发,那废话不多说,直接说步骤: 安装Djagno 安装Django Rest Framework 定义models 定义Rest framework的serializers 定义Rest framework的viewsets 配置Rest framework的...

osc_qo2uprmb
16分钟前
7
0
SQL注入原理及代码分析(一)

前言 我们都知道,学安全,懂SQL注入是重中之重,因为即使是现在SQL注入漏洞依然存在,只是相对于之前现在挖SQL注入变的困难了。而且知识点比较多,所以在这里总结一下。通过构造有缺陷的代码...

osc_axrkis5i
18分钟前
6
0
Tomcat启动流程简析

Tomcat是一款我们平时开发过程中最常用到的Servlet容器。本系列博客会记录Tomcat的整体架构、主要组件、IO线程模型、请求在Tomcat内部的流转过程以及一些Tomcat调优的相关知识。 力求达到以下...

osc_5c67s863
19分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部