复杂网络中的瓶颈点

背景

在一个由城市和道路构成的复杂网络中，城市之间通过有向道路相连接，每条道路都有一个交通量表示。你被要求确定网络中最重要的“瓶颈点”。瓶颈点是指，通过该城市所经过的所有道路中，最小的交通量对整体网络流动性影响最大。换句话说，如果该瓶颈点被切断，可能会导致网络的连通性发生显著变化。

此外，你还需要根据不同的条件（如城市间的最短路径、城市连通性等）进行查询并更新网络。

问题描述

给定一个有向图，其中每条边表示一条城市之间的道路，边的权重表示该道路的交通量。你需要通过查询来确定：

1. 每对城市之间的最短路径（考虑边的交通量）。
2. 网络中的瓶颈点，瓶颈点的定义是连接该城市的所有道路中的最小交通量。

你需要实现一个高效的算法来处理这些查询。

输入

• 第一行输入两个整数 n 和 m（2 ≤ n ≤ 10^5，1 ≤ m ≤ 2 × 10^5），表示城市数和道路数。
• 接下来的 m 行，每行包含三个整数 u, v, 和 w（1 ≤ u, v ≤ n，1 ≤ w ≤ 10^6），表示有一条从城市 u 到城市 v 的道路，交通量为 w。
• 接下来的一行输入一个整数 q（1 ≤ q ≤ 10^5），表示查询的数量。
• 接下来的 q 行，每行表示一个查询：
  • 查询类型 1：1 u v，表示查询从城市 u 到城市 v 的最短路径的交通量。
  • 查询类型 2：2 u，表示查询城市 u 的瓶颈点交通量，瓶颈点定义为从城市 u 出发的所有边中的最小交通量。

输出

对于每个查询：

• 对于查询类型 1，输出从城市 u 到城市 v 的最短路径的交通量。如果两城市之间不可达，输出 -1。
• 对于查询类型 2，输出城市 u 的瓶颈点交通量。如果城市 u 没有出发的道路，输出 -1。

样例输入

import random

# 生成随机图数据和查询
def generate_graph_data(n, m, q):
    # 图的城市和道路
    edges = []
    for _ in range(m):
        u = random.randint(1, n)
        v = random.randint(1, n)
        # 避免自环
        while u == v:
            v = random.randint(1, n)
        w = random.randint(1, 10**6)  # 道路的交通量
        edges.append((u, v, w))
    
    # 查询生成
    queries = []
    for _ in range(q):
        query_type = random.randint(1, 2)
        if query_type == 1:
            u = random.randint(1, n)
            v = random.randint(1, n)
            queries.append(f"1 {u} {v}")
        elif query_type == 2:
            u = random.randint(1, n)
            queries.append(f"2 {u}")
    
    # 格式化输出数据
    graph_data = f"{n} {m}\n"
    for u, v, w in edges:
        graph_data += f"{u} {v} {w}\n"
    
    graph_data += f"{q}\n"
    for query in queries:
        graph_data += query + "\n"
    
    return graph_data

# 参数：城市数 n，边数 m，查询数 q
n = 1000  # 城市数
m = 3000  # 边数
q = 1000  # 查询数

# 生成数据
data = generate_graph_data(n, m, q)

# 输出生成的数据
with open("graph_data.txt", "w") as file:
    file.write(data)

print("数据生成完毕，已保存为 graph_data.txt 文件。")

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

// 边的结构体表示
struct Edge {
    int to, weight;
};

class Graph {
private:
    int n; // 城市数
    vector<vector<Edge>> adjList; // 邻接表

public:
    Graph(int n) {
        this->n = n;
        adjList.resize(n + 1); // 城市编号从1到n
    }

    // 添加道路
    void addEdge(int u, int v, int w) {
        adjList[u].push_back({v, w});
    }

    // Dijkstra 算法求最短路径
    vector<int> dijkstra(int start) {
        vector<int> dist(n + 1, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            int d = pq.top().first;
            pq.pop();

            if (d > dist[u]) continue;

            for (const Edge& e : adjList[u]) {
                int v = e.to, weight = e.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    }

    // 查询城市 u 的瓶颈点交通量
    int getBottleneck(int u) {
        if (adjList[u].empty()) return -1;
        
        int minWeight = INT_MAX;
        for (const Edge& e : adjList[u]) {
            minWeight = min(minWeight, e.weight);
        }
        return minWeight;
    }
};

int main() {
    int n, m, q;
    cin >> n >> m;

    Graph g(n);

    // 输入边数据
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g.addEdge(u, v, w);
    }

    cin >> q;

    // 处理查询
    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;

        if (type == 1) {
            int u, v;
            cin >> u >> v;

            // 计算从 u 到 v 的最短路径
            vector<int> dist = g.dijkstra(u);
            if (dist[v] == INT_MAX) {
                cout << -1 << endl; // 不可达
            } else {
                cout << dist[v] << endl;
            }
        } else if (type == 2) {
            int u;
            cin >> u;

            // 查询城市 u 的瓶颈点
            int bottleneck = g.getBottleneck(u);
            cout << bottleneck << endl;
        }
    }

    return 0;
}