专题·最短路径树【including 例题

初见安~本专题前置知识：最短路

最短路径树是什么？就是最短路构成的树。【啪！

举个例子：

假设我们要求的是从1出发的最短路径树，那么我们就先求出最短路并标记用到了的边：

很明显，这些最短路是一定可以连城一棵以1为根的树的。这棵树就是最短路径树。

最短路径树有什么用？先看一个入门题目吧——

最短路径树入门

Description

n个城市用m条双向公路连接，使得任意两个城市都能直接或间接地连通。其中城市编号为1..n，公路编号为1..m。
任意个两个城市间的货物运输会选择最短路径，把这n*(n-1)条最短路径的和记为S。现在你来寻找关键公路r，公
路r必须满足：当r堵塞之后，S的值会变大（如果r堵塞后使得城市u和v不可达，则S为无穷大）。

Input

第1行包含两个整数n,m，
接下来的m行，每行用三个整数描述一条公路a,b,len（1<=a,b<=n），
表示城市a和城市b之间的公路长度为len，这些公路依次编号为1..m。
n<=100，1<=m<=3000，1<=len<=10000。

Output

从小到大输出关键公路的编号。

Sample Input

4 6 
1 2 1 
2 3 1 
3 4 1 
1 4 1 
1 3 1 
4 1 1

Sample Output

1
2
3
5

Sol

说白了就是求有多少条边是所有最短路的必经边。这是很典型的一个最短路径树的应用。

因为这里涉及到很多条最短路，所以我们分别以1~n的每个点作为根求一边最短路径树，然后枚举树上的边，只要某条边删去后再得到的最短路之和大于了先前求出来的最短路径，那么这就是一条必经边。加之需要输出边的编号，我们可以另开一个数组fa，用fa[ i ]表示节点 i 连出去的被选中的一条离根更近的边。在这个信息下，我们就可以枚举这条最短路上的每条边了。

也就是说，我们O(n)下要求n次最短路，而后再是n次最短路……复杂度之高，但是n很小，而且就这道题而言，时限有3s，所以不慌~

下面上代码——【实测：求最短路部分，用SPFA 1000+ms，Dijkstra 2100+ms】

#include<bits/stdc++.h>
#define maxn 105
#define maxm 3005
using namespace std;
int n, m, sum = 0, ssum = 9; 
struct edge 
{
	int id, w, to;
	edge() {}
	edge(int d, int tt, int ww) {id = d, to = tt, w = ww;}
};

vector<edge> g[maxn];
int dis[maxn], fa[maxn];
void init()
{
	for(int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
}

bool vis[maxn];
void spfa1(int u)//纯粹的最短路 
{
	register int v, w, id;
	vis[u] = 1;
	queue<int> q; q.push(u);
	while(q.size())
	{
		u = q.front(); q.pop(); vis[u] = 0;
		for(int i = 0; i < g[u].size(); i++)
		{
			v = g[u][i].to, w = g[u][i].w, id = g[u][i].id;
			if(dis[v] <= dis[u] + w) continue;
			dis[v] = dis[u] + w;
			fa[v] = id;//记得标记前驱边，因为每个点的前驱边是唯一的 
			if(!vis[v]) q.push(v), vis[v] = 1;
		}
	}
}

void spfa2(int u, int flag)
{
	register int v, w, id;
	vis[u] = 1;
	queue<int> q; q.push(u);
	while(q.size())
	{
		u = q.front(); q.pop(); vis[u] = 0;
		for(int i = 0; i < g[u].size(); i++)
		{
			v = g[u][i].to, w = g[u][i].w, id = g[u][i].id;
			if(id == flag) continue;//flag这条边我们标记了不选 
			if(dis[v] <= dis[u] + w) continue;
			dis[v] = dis[u] + w;//第二次不能再更新fa，其他操作如旧 
			if(!vis[v]) q.push(v), vis[v] = 1;
		}
	}
}

bool mark[maxm];//注意mark的大小 
int main()
{
	scanf("%d%d", &n, &m);
	register int u, v, w;
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back(edge(i, v, w));//一定要记得存边的编号 
		g[v].push_back(edge(i, u, w));
	}
	
	for(int i = 1; i <= n; i++)
	{
		init();//每次一定要初始化 
		fa[i] = 0, dis[i] = 0, sum = 0;
		spfa1(i);//以i为根求最短路径树 
		for(int k = 1; k <= n; k++) sum += dis[k];//先求一次最短路径和 
		for(int j = 1; j <= n; j++)//枚举每条边 
		{
			if(!fa[j] || mark[fa[j]]) continue;//已经确定了或者！fa，也就相当于j == i 
			ssum = 0; 
			init(); dis[i] = 0;
			spfa2(i, fa[j]);//再求一次最短路 
			for(int k = 1; k <= n; k++) ssum += dis[k];
			if(ssum > sum) mark[fa[j]] = 1;//符合题意，此为必经边 
		}
	}
	bool cnt = 0;
	for(int i = 1; i <= m; i++)
		if(mark[i]) printf("%d\n", i);
	return 0;
}

关于最短路径树，还有一个关于求有多少条最短路的典型例题——黑暗城堡【传送门建设中】

以上就是全部内容啦~~~

迎评：）
——End——