# 计算机23级数据结构上级实验（第7周）
A 去火车站
寒假到了，小明准备坐火车回老家，现在他从学校出发去火车站，CC市去火车站有两种方式：轻轨和公交车。小明为了省钱，准备主要以乘坐公交为主。CC市还有一项优惠政策，持学生证可以免费乘坐一站轻轨（但只能乘坐一站）。小明想尽快到达火车站，请编写程序为小明找到一条从学校到火车站最快的路线及换乘轻轨的方案。
假设换乘时间忽略不计，公交车与轻轨站点相同，但线路和速度不一定相同，所有线路都是双向的。可以第一站就乘坐轻轨，也可以最后一站乘坐轻轨，也可以在中间某站坐轻轨。如果乘坐轻轨和不乘坐轻轨到达火车站的时间相同，则无需换乘轻轨。最多坐一站轻轨。
输入格式:
输入包含多组数据。每组数据第一行为3个整数n、s和t，分别表示车站数（编号为1至n），小明学校所在的站和火车站所在的站。下一行为一个整数m，表示公交车的线路信息，接下来m行，每行为3个正整数a、b、c，表示公交车从a站到b站需要c分钟。下一行为一个整数k，表示轻轨的线路信息，接下来k行，每行为3个正整数x、y、z，表示轻轨从x站到y站需要z分钟。所有整数均不超过20000。
输出格式:
对每组数据输出2行。第1行为1个整数T，表示从学校到达火车站的最短时间；第2行为一个整数K，表示在站点K换乘轻轨，若有多个可能的换乘点，则输出编号最小者，如果无需换乘轻轨，则第二行输出“no metro”。
输入样例:
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
输出样例:
5
2
5
2
- 首次考虑多次替换地铁路后通过Dijkstra重新计算,但是在数据量大时会超时
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
// 边结构体，表示图中的边：v 表示目标顶点，w 表示边的权重
class edge {
public:
int v, w;
edge(int _v, int _w) : v(_v), w(_w) { }
};
// 图的邻接表表示
vector<vector<edge>> bus; // 图的邻接表，bus[u] 存储与顶点 u 相连的所有边
vector<int> dist; // dist[i] 表示从起点到顶点 i 的最短距离
int mindist, takemetro; // mindist 存储最短距离，takemetro 存储选择的地铁的编号
// 向图中添加边
void addedge(vector<vector<edge>>& vextices, int u, int v, int w) {
edge p(v, w); // 创建一条从 u 到 v 权重为 w 的边
vextices[u].push_back(p); // 将边加入邻接表
}
// 创建图：读取边的信息并构建邻接表
void CreateGraph(vector<vector<edge>>& vextices, int n) {
int e;
cin >> e; // 输入边数
vextices.resize(n + 1); // 图的顶点编号从 1 到 n，所以需要 n + 1 个空间
dist.resize(n + 1, INT_MAX); // 初始化所有顶点的最短距离为无穷大
// 读取所有边并构建图的邻接表
for (int i = 0; i < e; i++) {
int u, v, w;
cin >> u >> v >> w; // 输入边 u, v 和权重 w
addedge(vextices, u, v, w); // 添加边 u -> v
addedge(vextices, v, u, w); // 添加边 v -> u (无向图)
}
}
// 使用优先队列（最小堆）实现 Dijkstra 算法，求从起点到所有其他顶点的最短路径
void queue_ShortPath(int start, const vector<vector<edge>> bus) {
dist.assign(bus.size(), INT_MAX); // 重置距离数组
dist[start] = 0; // 起点到自身的距离为 0
// 优先队列，存储 (距离, 节点)
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, start }); // 将起点放入队列
// 队列不为空时进行处理
while (!pq.empty()) {
int d = pq.top().first; // 当前最短路径
int u = pq.top().second; // 当前顶点
pq.pop(); // 弹出队列
// 如果当前路径已经不是最短路径，则跳过
if (d > dist[u]) continue;
// 更新所有与 u 相邻的顶点的最短路径
for (int i = 0; i < bus[u].size(); i++) {
auto e = bus[u][i]; // 获取与 u 相邻的边
int v = e.v; // 相邻顶点 v
int w = e.w; // 边的权重
// 如果通过 u 访问 v 的路径更短，则更新 v 的最短路径
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
// 将新的最短路径加入优先队列
pq.push({ dist[v], v });
}
}
}
}
// 计算从起点 s 到终点 t 的最短路径，并考虑地铁路线的影响
void find(int s, int t) {
// 先计算不使用地铁时的最短路径
queue_ShortPath(s, bus);
if (dist[t] < mindist) mindist = dist[t]; // 更新最短距离
takemetro = INT_MAX; // 初始化地铁编号为无穷大
int k;
cin >> k; // 输入地铁线路的数量
for (int q = 0; q < k; q++) {
int u, v, w;
cin >> u >> v >> w; // 输入地铁线路的起点 u，终点 v 和权重 w
int metro = u < v ? u : v; // 选择较小的顶点编号作为地铁线路的编号
// 如果通过地铁能更短到达终点，则考虑使用该地铁
if (dist[u] + w <= dist[v]) {
addedge(bus, u, v, w); // 添加地铁边
addedge(bus, v, u, w); // 添加地铁边
// 重新计算最短路径
queue_ShortPath(s, bus);
// 判断是否更新最短距离
if (dist[t] == mindist && takemetro != INT_MAX) {
takemetro = min(takemetro, metro); // 如果距离相同，选择地铁编号最小的
}
else if (dist[t] < mindist) {
mindist = dist[t]; // 更新最短路径
takemetro = metro; // 更新选择的地铁编号
}
// 移除刚才添加的地铁边
bus[u].pop_back();
bus[v].pop_back();
}
}
// 输出结果
cout << mindist << endl; // 输出最短路径
if (takemetro != INT_MAX) cout << takemetro << endl; // 输出选择的地铁编号
else cout << "no metro" << endl; // 如果没有使用地铁，则输出 "no metro"
}
// 清除图的相关信息，为下一次查询做准备
void Clear() {
bus.clear(); // 清空邻接表
dist.clear(); // 清空最短路径数组
mindist = INT_MAX; // 初始化最短路径为无穷大
takemetro = INT_MAX; // 初始化地铁编号为无穷大
}
int main() {
int n, s, t;
while (cin >> n >> s >> t) { // 输入顶点数 n 和查询的起点 s、终点 t
Clear(); // 清除旧数据
CreateGraph(bus, n); // 创建图
find(s, t); // 查找从 s 到 t 的最短路径
}
}
- 利用Dijkstra原理，即最优路由局部最优路组成
- 进行两次Dijkstra算法，分别从起始点和结束点出发，记录到地铁两端的局部最优路
- 所以每次有新的地铁可以直接利用上述条件，加上权值构成新的路与目前最短路比较
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
// 边结构体，表示图中的边：v 表示目标顶点，w 表示边的权重
class edge
{
public:
int v, w;
edge(int _v, int _w) : v(_v), w(_w) { }
};
// 图的邻接表表示
vector<vector<edge>> bus; // 正向图，bus[u] 存储与顶点 u 相连的所有边
vector<vector<edge>> anti; // 反向图，用于计算目的地到所有顶点的最短路径
vector<int> dist_start, dist_end; // dist_start 存储从起点到所有顶点的最短距离，dist_end 存储从终点到所有顶点的最短距离
int mindist, takemetro; // mindist 存储最短路径的距离，takemetro 存储选择的地铁线路编号
// 向图中添加边
void addedge(vector<vector<edge>>& vextices, int u, int v, int w)
{
edge p(v, w); // 创建一条从 u 到 v 权重为 w 的边
vextices[u].push_back(p); // 将边加入邻接表
}
// 创建图：读取边的信息并构建邻接表
void CreateGraph(int n)
{
int e;
cin >> e; // 输入边数
bus.resize(n + 1); // 初始化 bus 邻接表
anti.resize(n + 1); // 初始化 anti 邻接表（反向图）
// 读取所有边并构建图的邻接表
for (int i = 0; i < e; i++)
{
int u, v, w;
cin >> u >> v >> w; // 输入边 u, v 和权重 w
addedge(bus, u, v, w); // 在正向图中添加边 u -> v
addedge(anti, v, u, w); // 在反向图中添加边 v -> u（即 u -> v 在反向图中表示 v -> u）
}
}
// 使用优先队列（最小堆）实现 Dijkstra 算法，求从起点到所有其他顶点的最短路径
void queue_ShortPath(int start, vector<int>& dist, const vector<vector<edge>> bus)
{
dist.assign(bus.size(), INT_MAX); // 重置距离数组
dist[start] = 0; // 起点到自身的距离为 0
// 优先队列，存储 (距离, 节点)
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, start }); // 将起点放入队列
// 队列不为空时进行处理
while (!pq.empty())
{
int d = pq.top().first; // 当前最短路径
int u = pq.top().second; // 当前顶点
pq.pop(); // 弹出队列
// 如果当前路径已经不是最短路径，则跳过
if (d > dist[u]) continue;
// 更新所有与 u 相邻的顶点的最短路径
for (int i = 0; i < bus[u].size(); i++)
{
auto e = bus[u][i]; // 获取与 u 相邻的边
int v = e.v; // 相邻顶点 v
int w = e.w; // 边的权重
// 如果通过 u 访问 v 的路径更短，则更新 v 的最短路径
if (dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
// 将新的最短路径加入优先队列
pq.push({ dist[v], v });
}
}
}
}
// 计算从起点 s 到终点 t 的最短路径，并考虑地铁线路的影响
void find(int s, int t)
{
// 先计算不使用地铁时的最短路径（正向图）
queue_ShortPath(s, dist_start, bus);
if (dist_start[t] < mindist) mindist = dist_start[t]; // 更新最短距离
takemetro = INT_MAX; // 初始化地铁编号为无穷大
// 计算反向图的最短路径，从终点 t 到所有顶点的最短路径
queue_ShortPath(t, dist_end, anti);
// 接下来处理所有地铁线路，判断是否能通过地铁优化路径
int k;
cin >> k; // 输入地铁线路的数量
for (int q = 0; q < k; q++)
{
int u, v, w;
cin >> u >> v >> w; // 输入地铁线路的起点 u，终点 v 和权重 w
int metro = u < v ? u : v; // 选择较小的顶点编号作为地铁线路的编号
// 计算通过地铁线路的路径
long long dist = dist_start[u] + dist_end[v] < dist_start[v] + dist_end[u] ?
dist_start[u] + dist_end[v] + w : dist_start[v] + dist_end[u] + w;
// 判断是否更新最短路径
if (dist == mindist && takemetro != INT_MAX)
{
takemetro = min(takemetro, metro); // 如果距离相同，选择地铁编号最小的
}
else if (dist < mindist)
{
mindist = dist; // 更新最短路径
takemetro = metro; // 更新选择的地铁编号
}
}
// 输出结果
cout << mindist << endl; // 输出最短路径
if (takemetro != INT_MAX) cout << takemetro << endl; // 输出选择的地铁编号
else cout << "no metro" << endl; // 如果没有使用地铁，则输出 "no metro"
}
// 清除图的相关信息，为下一次查询做准备
void Clear()
{
bus.clear(); // 清空邻接表
anti.clear(); // 清空反向图邻接表
dist_start.clear(); // 清空最短路径数组
dist_end.clear(); // 清空反向最短路径数组
mindist = INT_MAX; // 初始化最短路径为无穷大
takemetro = INT_MAX; // 初始化地铁编号为无穷大
}
int main()
{
int n, s, t;
while (cin >> n >> s >> t) { // 输入顶点数 n 和查询的起点 s、终点 t
Clear(); // 清除旧数据
CreateGraph(n); // 创建图
find(s, t); // 查找从 s 到 t 的最短路径
}
}
B 联盟数目
艾迪是一家集团公司的老板，该集团包含n家公司，为了管理公司，艾迪会时常通过网络向各公司发送消息。各公司间的网络是单向的，每个公司都有一个分发列表，表示其能向哪些公司直接传达消息。例如A公司的分发列表为B、C，表示A可将消息直接传送给B和C（由于网络是单向的，B或C不一定能向A传送消息），这样艾迪若想向A、B、C公司发送消息，则只需向A发送消息即可，随后A可将消息传送到B和C。
为了便于管理各公司，艾迪打算将n家公司分成若干组，每组称为一个区域联盟，每组满足如下条件：组内的任意公司消息互相可达。即对于组内任意公司u和v，u可将消息传送到v（可由u直接传送到v，也可通过组内其他公司中转传送到v），v也可将消息传送到u。可以认为一个公司可以将消息传送给自己，即一个公司可以自成一组。
艾迪希望组的数量尽可能少，即在满足上述条件的情况下，每组包含的公司数目尽可能多。
现给定每个公司的分发列表，请编写程序告知艾迪，他的集团最少能分成多少组。
输入格式:
第一行包含一个整数T (1≤T≤100)表示数据组数。对于每组数据，第一行为一个整数n (2≤n≤100)，表示公司数目，公司编号为1到n。随后n行，第i行包含若干整数，表示第i个公司的分发列表，每行以0结尾。
输出格式:
对于每组数据，输出一行，为一个整数，表示组数。
输入样例:
3
5
2 4 3 0
4 5 0
0
0
1 0
3
2 0
0
2 1 0
3
2 0
3 0
0
输出样例:
3
3
3
模板题，即找有向图的强连通分量数
思路一：利用拓扑排序判断是否有环，但是比较繁琐不考虑实现
思路二：
Kosaraju 算法
引入
Kosaraju 算法最早在 1978 年由 S. Rao Kosaraju 在一篇未发表的论文上提出，但 Micha Sharir 最早发表了它。
过程
该算法依靠两次简单的 DFS 实现：
第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。
第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。
两次 DFS 结束后，得到强连通分量数，Kosaraju 算法的时间复杂度为O（n+m）
#include<iostream> #include<vector> using namespace std; // 图的邻接表表示，vextices存储原图的边，antivex存储反图的边 vector<vector<int>> vextices, antivex; // 添加边的函数，u->v void addedge(vector<vector<int>>& vextices, int u, int v) { vextices[u].push_back(v); // 将v添加到u的邻接表中 } // 创建图的函数 void CreateGraph() { int n; // 图中节点数 cin >> n; // 输入节点数 vextices.resize(n + 1); // 调整vextices大小，确保1-based indexing antivex.resize(n + 1); // 调整antivex大小，确保1-based indexing // 输入每个节点的邻接节点 for (int i = 1; i <= n; i++) { int v; cin >> v; // 读取与节点i相连的第一个节点 while (v != 0) // 如果节点不为0，则继续添加边 { addedge(vextices, i, v); // 在原图中添加边i->v addedge(antivex, v, i); // 在反图中添加边v->i cin >> v; // 读取下一个邻接节点 } } } // 深度优先搜索（DFS），用于原图，生成逆拓扑序列 void dfs1(int u, vector<bool>& vis, vector<int>& s) { vis[u] = true; // 标记节点u已访问 for (int i = 0; i < vextices[u].size(); i++) // 遍历u的所有邻接节点 { int v = vextices[u][i]; // 获取邻接节点v if (!vis[v]) // 如果v未被访问 dfs1(v, vis, s); // 递归访问v } s.push_back(u); // 将节点u添加到逆拓扑序列中 } // 深度优先搜索（DFS），用于反图，寻找强连通分量 void dfs2(int u, int& SccCnt, vector<int>& color) { color[u] = SccCnt; // 将节点u标记为当前强连通分量 for (int i = 0; i < antivex[u].size(); i++) // 遍历u的所有反向邻接节点 { int v = antivex[u][i]; // 获取反向邻接节点v if (!color[v]) // 如果v未被标记为强连通分量 dfs2(v, SccCnt, color); // 递归访问v } } // 主逻辑：使用Kosaraju算法计算强连通分量数 void Address() { vector<bool> vis; // 访问标记数组 vector<int> stack; // 存储逆拓扑序列 stack.push_back(0); // 初始时插入0，顶点从1开始 vector<int> color; // 存储每个节点的强连通分量编号 int sccCnt = 0; // 强连通分量计数器 vis.resize(vextices.size(), false); // 初始化访问标记数组 color.resize(vis.size()); // 初始化颜色标记数组 // 1. 执行原图上的DFS，生成逆拓扑序列 for (int i = 1; i < vextices.size(); i++) { if (!vis[i]) // 如果节点i未访问过 dfs1(i, vis, stack); // 对i进行深度优先搜索 } // 2. 执行反图上的DFS，计算强连通分量 //因为是逆拓扑序列，所以优先级大的点由出度多，变成了入度多，那么 DFS 过程中就会被反边堵住 for (int i = vextices.size() - 1; i > 0; i--) // 从逆拓扑序列的末尾开始遍历 { if (!color[stack[i]]) // 如果节点stack[i]还未被分配强连通分量 { ++sccCnt; // 强连通分量数加1 dfs2(stack[i], sccCnt, color); // 在反图上深度优先搜索，标记强连通分量 } } cout << sccCnt << endl; // 输出强连通分量的数量 } int main() { int T; // 输入测试用例数量 cin >> T; // 读取测试用例数量 for (int i = 0; i < T; i++) // 对每个测试用例执行操作 { vextices.clear(); // 清空邻接表 antivex.clear(); // 清空反图邻接表 CreateGraph(); // 创建图 Address(); // 计算强连通分量并输出结果 } return 0; }
Tarjan 算法
DFS 生成树
在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：
有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：
- 树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
- 反祖边（back edge）：示意图中以红色边表示（即 7 ->1 ），也被叫做回边，即指向祖先结点的边。
- 横叉边（cross edge）：示意图中以蓝色边表示（即 9 -> 7），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
- 前向边（forward edge）：示意图中以绿色边表示（即 3 ->6），它是在搜索的时候遇到子树中的结点的时候形成的。
我们考虑 DFS 生成树与强连通分量之间的关系。
如果结点 u是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 u为根的子树中。结点 u 被称为这个强连通分量的根。
反证法：假设有个结点v在该强连通分量中但是不在以u为根的子树中，那么u到v的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和v不在以u为根的子树中矛盾了。得证。
Tarjan 算法求强连通分量
Tarjan 算法基于对图进行 深度优先搜索。我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中
TARJAN_SEARCH(int u) vis[u]=true low[u]=dfn[u]=++dfncnt push u to the stack for each (u,v) then do if v hasn't been searched then TARJAN_SEARCH(v) // 搜索 low[u]=min(low[u],low[v]) // 回溯 else if v has been in the stack then low[u]=min(low[u],dfn[v])
int dfn[N], low[N], dfncnt; // dfn[i] 表示节点 i 的访问时间戳, low[i] 表示节点 i 能追溯到的最早时间戳 //dfncnt 是一个全局计数器，用来记录深度优先搜索（DFS）过程中节点的访问顺序 int s[N], in_stack[N], tp; // s 是模拟栈的数组，in_stack[i] 表示节点 i 是否在栈中, tp 是栈顶指针 int scc[N], sc; // scc[i] 表示节点 i 所属 SCC 的编号, sc 表示 SCC 的总数 int sz[N]; // sz[i] 表示第 i 个 SCC 的节点数 // Tarjan 算法主函数，输入当前节点 u void tarjan(int u) { // 初始化节点 u 的 dfn 和 low 值为当前时间戳，并将 u 压入栈中 low[u] = dfn[u] = ++dfncnt; s[++tp] = u; in_stack[u] = 1; // 遍历 u 的所有邻接节点 v for (int i = h[u]; i; i = e[i].nex) { const int &v = e[i].t; // v 是 u 的一个邻接节点 if (!dfn[v]) { // 如果 v 尚未被访问 tarjan(v); // 递归访问 v low[u] = min(low[u], low[v]); // 更新 u 的 low 值 } else if (in_stack[v]) { // 如果 v 在栈中 low[u] = min(low[u], dfn[v]); // 更新 u 的 low 值 } } // 如果当前节点 u 是一个 SCC 的根节点 if (dfn[u] == low[u]) { ++sc; // 新增一个 SCC // 将当前 SCC 的所有节点从栈中弹出 while (s[tp] != u) { scc[s[tp]] = sc; // 标记节点所属的 SCC 编号 sz[sc]++; // 更新当前 SCC 的节点数量 in_stack[s[tp]] = 0; // 将节点标记为不在栈中 --tp; // 弹出栈顶节点 } // 处理栈中的根节点 u scc[s[tp]] = sc; sz[sc]++; in_stack[s[tp]] = 0; --tp; // 弹出根节点 } }补充
分量标号和拓扑序的关系
Tarjan 算法在处理过程中，实际上是按照某种 逆拓扑序 来发现强连通分量的，这是因为算法在深度优先搜索的过程中会先访问那些没有出边的节点，而这与拓扑排序的过程是相反的。
如果我们将图中的所有强连通分量缩成单个节点，那么在这些缩点后的节点形成的 DAG 中进行拓扑排序，得到的顺序将与 Tarjan 算法给出的强连通分量的标号顺序相反。
因此，可以说，在缩点后的 DAG 中，强连通分量（缩点后）的标号顺序是其拓扑序的逆序。但要注意的是，这种说法仅在考虑了强连通分量之间的依赖关系（即从一个强连通分量到另一个强连通分量的有向边）时才成立。单个强连通分量内部的节点由于存在环，所以内部并不满足拓扑序的定义。
Garbow 算法
过程
Garbow 算法是 Tarjan 算法的另一种实现，Tarjan 算法是用 dfn 和 low 来计算强连通分量的根，Garbow 维护一个节点栈，并用第二个栈来确定何时从第一个栈中弹出属于同一个强连通分量的节点。从节点u开始的 DFS 过程中，当一条路径显示这组节点都属于同一个强连通分量时，只要栈顶节点的访问时间大于根节点w的访问时间，就从第二个栈中弹出这个节点，那么最后只留下根节点
。在这个过程中每一个被弹出的节点都属于同一个强连通分量。当回溯到某一个节点w时，如果这个节点在第二个栈的顶部，就说明这个节点是强连通分量的起始节点，在这个节点之后搜索到的那些节点都属于同一个强连通分量，于是从第一个栈中弹出那些节点，构成强连通分量。
int garbow(int u) {
// 将当前节点 u 压入两个栈中
stack1[++p1] = u; // 栈 1，用于记录当前递归路径中的节点
stack2[++p2] = u; // 栈 2，用于确定 SCC 的根节点
low[u] = ++dfs_clock; // 为节点 u 设置访问时间戳
// 遍历 u 的所有邻接节点 v
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; // 获取邻接节点 v
if (!low[v]) {
// 如果 v 未被访问，递归访问 v
garbow(v);
} else if (!sccno[v]) {
// 如果 v 尚未属于任何 SCC，更新 stack2 的栈顶元素
while (low[stack2[p2]] > low[v]) p2--;
}
}
// 如果 stack2 栈顶是当前节点 u，则找到了一个 SCC
if (stack2[p2] == u) {
p2--; // 从 stack2 中移除 u
scc_cnt++; // 新增一个 SCC
// 从 stack1 中弹出属于当前 SCC 的所有节点
do {
sccno[stack1[p1]] = scc_cnt; // 将节点标记为当前 SCC
// 可在此处增加代码统计每个 SCC 的大小，例如: all_scc[scc_cnt]++;
} while (stack1[p1--] != u); // 直到弹出当前 SCC 的根节点 u
}
return 0; // 返回值无实际用途，递归的函数签名需要返回值
}
void find_scc(int n) {
// 初始化全局变量
dfs_clock = scc_cnt = 0; // 重置时间戳和 SCC 计数器
p1 = p2 = 0; // 栈指针初始化为 0
memset(sccno, 0, sizeof(sccno)); // sccno 数组清零，表示所有节点未分配 SCC
memset(low, 0, sizeof(low)); // low 数组清零，表示所有节点未访问
// 遍历所有节点，调用 Gabow 算法
for (int i = 1; i <= n; i++) {
if (!low[i]) garbow(i); // 对未访问的节点调用 garbow
}
}
C 社交网络
可以将n个QQ用户间的好友关系建模为一个包含n个顶点的无向图，顶点编号为1至n，每个顶点对应一个用户，若2个用户i和j是QQ好友，则在顶点i和j之间连接一条边，并根据用户间的亲密度对该边附以一个权值c**ij。在该图中，可以利用两个顶点间的最短路径长度衡量两个用户的关系密切程度，也可以利用经过一个顶点的最短路径数目来衡量一个用户在关系网络中的影响力，具体地，我们定义用户k在QQ关系网络中的“影响力”为：
其中N**ij为顶点i到j的最短路径数目，N**ijk为顶点i到j的所有最短路径中经过顶点k的最短路径数目（上述二值可能超出int型范围，请使用long long类型）。D**ij表示i到j的最短路径长度。
现给定一个如上描述的无向图，请编写程序，计算每个顶点的“影响力”，假定给定的图是连通的。
输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，接下来e行表示每条边的信息，每行为3个正整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。
n≤100，e≤5000，c≤1000，任意两点间的最短路径数目≤1010
输出格式:
输出为n行，每行一个实数，精确到小数点后3位，第i行为顶点i的影响力。
输入样例:
4 4
3 2 6
4 3 1
1 3 9
4 1 1
输出样例:
0.000
0.000
30.000
20.000
解释:
对于顶点1：边2-3、3-4、2-4的最短路径均不经过顶点1，故顶点1的影响力为0.
对于顶点3： 顶点1到2的最短路径共1条，长度为8，经过点3，顶点2到4的最短路径共1条，长度为7，经过点3，顶点1到4的最短路径共1条，但不经过点3。 故f(3)=D12∗1+D24∗1+D14∗0+D21∗1+D42∗1+D41∗0=8+7+0+8+7+0=30.000
提示:
若顶点a到顶点b有x条路径，点b到点c有y条路径，则a经过b到达c的路径有x*y条。
类似 洛谷 P2047 [NOI2007] 社交网络
利用Folyd找各个点之间的最短距离，并在过程里更新最短距离的数量
核心
```cpp } //有路才进入判断
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) { // 如果找到更短的路径 if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; nums[i][j] = nums[i][k] * nums[k][j]; // 路径数的更新 } // 如果有相等的最短路径，增加路径数 else if (dist[i][k] + dist[k][j] == dist[i][j]) { nums[i][j] += nums[i][k] * nums[k][j]; // 路径数的累加 }```
接着找经过k的最短距离数
//找从i到j经过k的最短路 if (dist[i][k] + dist[k][j] == dist[i][j]) { f[k] += dist[i][j]*(1.0 * nums[i][k] * nums[k][j]) / nums[i][j]; }
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<vector<int>> graph; // 图的邻接矩阵表示，存储边的权重
vector<long double> f; // 用于存储每个节点的中介中心性（betweenness centrality）
// 创建图的邻接矩阵
void CreateGraph()
{
int n, e; // n 为节点数，e 为边数
cin >> n >> e;
graph.resize(n + 1, vector<int>(n + 1, INT_MAX)); // 初始化为无穷大
f.resize(n + 1, 0); // 初始化中心性数组为 0
// 自身到自身的距离为 0
for (int i = 1; i < graph.size(); i++)
{
graph[i][i] = 0;
}
// 输入边的信息并填充邻接矩阵
for (int i = 0; i < e; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a][b] = c; // 边 a -> b 的权重
graph[b][a] = c; // 边 b -> a 的权重（无向图）
}
}
vector<vector<int>> dist; // 存储最短路径的长度
vector<vector<long long>> nums; // 存储最短路径的条数
// Floyd-Warshall 算法，计算任意两点间的最短路径和路径数
void Folyd() {
// 初始化 dist 和 nums，与邻接矩阵大小一致
dist.resize(graph.size(), vector<int>(graph.size(), INT_MAX));
nums.resize(graph.size(), vector<long long>(graph.size(), 0));
// 初始化 dist 和 nums
for (int i = 1; i < graph.size(); i++)
{
for (int j = 1; j < graph.size(); j++)
{
if (graph[i][j] < INT_MAX)
{
dist[i][j] = graph[i][j]; // 距离初始化为邻接矩阵中的权重
nums[i][j] = 1; // 初始每条边只有一条路径
}
}
dist[i][i] = 0; // 自身到自身的距离为 0
nums[i][i] = 0; // 自身到自身没有路径
}
// Floyd-Warshall 核心部分
for (int k = 1; k < graph.size(); k++) {
for (int i = 1; i < graph.size(); i++) {
if (i == k) continue; // 避免自身到自身
for (int j = 1; j < graph.size(); j++) {
if (j == k || i == j) continue; // 避免环路
// 有效路径才能进入判断
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
{
// 如果找到更短路径
if (dist[i][k] + dist[k][j] < dist[i][j])
{
dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短路径长度
nums[i][j] = nums[i][k] * nums[k][j]; // 更新路径数
}
// 如果有相等的最短路径，累加路径数
else if (dist[i][k] + dist[k][j] == dist[i][j])
{
nums[i][j] += nums[i][k] * nums[k][j];
}
}
}
}
}
}
// 计算中介中心性
void Address() {
for (int k = 1; k < graph.size(); k++)
{
for (int i = 1; i < graph.size(); i++)
{
if (i == k) continue; // 跳过自身
for (int j = 1; j < graph.size(); j++)
{
if (j == k || i == j) continue; // 跳过环路
// 如果 k 在 i 到 j 的最短路径上
if (dist[i][k] + dist[k][j] == dist[i][j])
{
// 累加 k 的中介中心性
f[k] += dist[i][j] * (1.0 * nums[i][k] * nums[k][j]) / nums[i][j];
}
}
}
// 输出 k 的中心性值，保留 3 位小数
printf("%.3llf\n", f[k]);
}
}
int main()
{
CreateGraph(); // 创建图
Folyd(); // 执行 Floyd-Warshall 算法
Address(); // 计算并输出每个节点的中介中心性
}
评论区 - 计算机23级数据结构上级实验（第7周）