[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

{

	int x, y, z;

	node(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}

}p[N << 1];

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

inline void add(int x, int y, int z)

{

	to[cnt] = y;

	val[cnt] = z;

	next[cnt] = head[x];

	head[x] = cnt++;

}

inline void dijkstra()

{

	int i, u, v;

	memset(dis, 127, sizeof(dis));

	dis[1] = 0;

	q.push(make_pair(0, 1));

	while(!q.empty())

	{

		u = q.top().second;

		q.pop();

		if(vis[u]) continue;

		vis[u] = 1;

		for(i = head[u]; i ^ -1; i = next[i])

		{

			v = to[i];

			if(dis[v] > dis[u] + val[i])

			{

				dis[v] = dis[u] + val[i];

				q.push(make_pair(dis[v], v));

			}

		}

	}

}

inline void dfs(int u, int d)

{

	int i, v;

	deep[u] = d;

	for(i = head[u]; i ^ -1; i = next[i])

	{

		v = to[i];

		if(dis[v] == dis[u] + val[i])

		{

			vis[i] = vis[i ^ 1] = 1;

			pre[v] = u;

			dfs(v, d + 1);

		}

	}

}

inline bool cmp(node x, node y)

{

	return dis[x.x] + dis[x.y] + x.z < dis[y.x] + dis[y.y] + y.z;

}

inline int find(int x)

{

	return x == f[x] ? x : f[x] = find(f[x]);

}

int main()

{

	int i, j, x, y, z, u, v;

	n = read();

	m = read();

	memset(head, -1, sizeof(head));

	for(i = 1; i <= m; i++)

	{

		x = read();

		y = read();

		z = read();

		add(x, y, z);

		add(y, x, z);

	}

	dijkstra();

	memset(vis, 0, sizeof(vis));

	dfs(1, 1);

	for(u = 1; u <= n; u++)

		for(i = head[u]; i ^ -1; i = next[i])

		{

			if(vis[i]) continue;

			v = to[i];

			vis[i] = vis[i ^ 1] = 1;

			p[++tot] = node(u, v, val[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++)

	{

		x = p[i].x;

		y = p[i].y;

		g.clear();

		while(x ^ y)

		{

			if(deep[x] < deep[y]) x ^= y ^= x ^= y;

			if(ans[x] <= 1e9) x = find(x);

			else

			{

				ans[x] = dis[p[i].x] + dis[p[i].y] + p[i].z - dis[x];

				g.push_back(x);

				x = pre[x];

			}

		}

		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;

}

巴特西

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

最新文章

热门文章