[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））

传送门

蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。

首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径

因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs求出最短路径树

发现，需要给这课树加边，才能有别的路径到达一个点x

那么我们连接树上两个节点u，v，边权为w

发现，u，v到两点公共祖先的路径上的所有点（除去lca）的答案都会受到影响

且ans[i] = dis[u] + dis[v] + w dis[i]

要使得ans最小，需要dis[u] + dis[v] + w最小，

那么直接树剖暴力修改不就好了？

另一种思路

我们可以把所有非树边取出，以dis[u] + dis[v] + w为关键字排一下，

显然，每一个点都只会求解一次，往后都不会更新答案

可以用并查集，已经更新答案的点就用并查集连接到lca，下次遇到已经更新过的点直接往上跳即可

找lca的过程和树剖类似

时间复杂度比树剖不知道高到哪里去了！

网上还有一些用左偏树或是单调队列做的，看样子好高深，蒟蒻没搞懂。。

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 200001 #define heap pair<int, int> using namespace std; int n, m, cnt, tot; int head[N], to[N << 1], val[N << 1], next[N << 1], dis[N], deep[N], ans[N], pre[N], f[N]; bool vis[N << 1]; priority_queue <heap, vector <heap>, greater <heap> > q; vector <int> g; struct node }p[N << 1]; inline int read() inline void add(int x, int y, int z) inline void dijkstra() } } } inline void dfs(int u, int d) } } inline bool cmp(node x, node y) inline int find(int x) int main() dijkstra(); memset(vis, 0, sizeof(vis)); dfs(1, 1); for(u = 1; u <= n; u++) for(i = head[u]; i ^ 1; i = next[i]) sort(p + 1, p + tot + 1, cmp); memset(ans, 127, sizeof(ans)); for(i = 1; i <= n; i++) f[i] = i; for(i = 1; i <= tot; i++) } for(j = 0; j < g.size(); j++) f[g[j]] = find(x); } for(i = 2; i <= n; i++) printf("%d\n", ans[i] <= 1e9 ? ans[i] : 1); return 0; }

　　

上一篇：[BZOJ3339] Rmq Problem（线段树）

下一篇：[BZOJ2733] [HNOI2012]永无乡（并查集 + 线段树合并）

---

stl 线段树 dfs 最短路 并查集 堆 dijkstra 树链剖分