烟台住房和城乡建设局网站,推广网店的途径和方法,传媒公司商业计划书,wordpress文字摘要题意分析
有一个 n n n 个点#xff0c; n − 1 n-1 n−1 条边的无向图#xff0c;边权均为 1 1 1。
每个点隶属于一个集合#xff0c;同一个集合的点可以互相传送。
给定 m m m 个询问#xff0c;求 x , y x, y x,y 的最短距离。
最短路解法
步骤#xff1a;
建…
题意分析
有一个 n n n 个点 n − 1 n-1 n−1 条边的无向图边权均为 1 1 1。
每个点隶属于一个集合同一个集合的点可以互相传送。
给定 m m m 个询问求 x , y x, y x,y 的最短距离。
最短路解法
步骤
建图。对于所有询问各跑一次最短路算法。
可选用的最短路算法
Spfa单次时间复杂度 O ( n ) ∼ O ( n 2 ) O(n) \sim O(n^2) O(n)∼O(n2)总时间复杂度 O ( n 2 ) ∼ O ( n 3 ) O(n^2) \sim O(n^3) O(n2)∼O(n3)。Dijkstra单词时间复杂度 O ( n log n ) O(n\log n) O(nlogn)总时间复杂度 O ( n 2 log n ) O(n^2\log n) O(n2logn)。
01 BFS 解法
观察发现本题仅存在边权为 0 0 0 和 1 1 1 的边故上述最短路算法存在多余开销我们考虑使用 BFS 算法进行求解并使用 deque 进行维护。
进行扩展时若是边权为 0 0 0 的边则放入队头反之放入队尾。
最坏时每条边均扩展 n n n 个点单次时间复杂度 O ( n 2 ) O(n^2) O(n2)总时间复杂度 O ( n 3 ) O(n^3) O(n3)。
BFS 解法
样例如下 我们用虚线表示同一个组别中的连线。 合并 1 , 4 1, 4 1,4 合并 2 , 6 2, 6 2,6 合并 3 , 5 3, 5 3,5 那么在合并之后当我们要算两个点之间的最短距离时可以直接用 BFS 算法解决。
观察上图发现因为组别内的点的边权为 0 0 0所以我们可以将所有同一个组别的点进行合并将点于点之间的最短路转换为组别于组别之间的最短路。
单词时间复杂度 O ( n ) O(n) O(n)总时间复杂度 O ( n 2 ) O(n^2) O(n2)。
#include iostream
#include cstring
#include algorithm
#include cstdio
#include queue
#include vectorusing namespace std;const int N 5e3 10, M N * 4;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int belong[N];
vectorint g[N];
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}void bfs(int u, int v)
{memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[u] 0;queueint q;q.push(u);while (q.size()){auto t q.front();q.pop();for (int i h[t]; ~i; i ne[i] ){int j e[i];if (dist[j] dist[t] w[i]){dist[j] dist[t] w[i];q.push(j);}}}cout dist[v] endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin n m;memset(h, -1, sizeof h);for (int i 1; i n; i ){int x;cin x;belong[i] x;g[x].push_back(i);}for (int i 1; i n; i ){int a, b;cin a b;a belong[a], b belong[b];add(a, b, 1), add(b, a, 1);}while (m -- ){int a, b;cin a b;bfs(belong[a], belong[b]);}return 0;
}
【在线测评】
