服务逃生(隐藏)-困难-其他,排序

题目

小明需要在多个业务节点之间选择最快的逃生节点集，并考虑每个节点的剩余业务容量。具体规则如下：

1. 输入描述：
   • 第1行：业务节点数 n（节点编号从0开始）。

   • 第2到n+1行：网络时延矩阵 delayMatrix，delayMatrix[i][j] 表示节点 i 到节点 j 的通信时延。

   ◦ 如果节点 i 和 j 之间没有直接相连的边，则 delayMatrix[i][j] = -1。

   ◦ 节点到自身的时延也是 -1。

   ◦ 时延范围为 [1, 100]。

   • 第n+2行：各节点的剩余容量 remainingCapacity，remainingCapacity[i] 表示节点 i 的剩余业务容量。

   ◦ 剩余容量范围为 [0, 100]。

   • 第n+3行：故障节点编号 faultyNode（取值范围 [0, n-1]）。

   • 第n+4行：受损业务量 damagedCapacity（取值范围 (0, 1000]）。

2. 输出描述：
   • 返回符合条件的逃生路径节点编号列表（用空格分隔）。

   • 选择逃生节点的规则：

   ◦ 逃生路径的时延最小。

   ◦ 逃生节点集的剩余容量总和 ≥ damagedCapacity。

   ◦ 如果多个节点到故障节点的最短时延相同，优先选择编号较小的节点。

   ◦ 如果逃生节点集中多个节点的最短时延相同，按编号从小到大排列。

   • 如果所有节点的剩余容量总和都不够容纳 damagedCapacity，则输出所有节点。

3. 样例输入：

   4
   -1 5 -1 8
   5 -1 1 3
   -1 1 -1 4
   8 3 4 -1
   10 20 15 25
   2
   12

4. 样例输出：

   1

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>using namespace std;vector<int> dijkstra(const vector<vector<int>>& delayMatrix, int src, int n) {vector<int> dist(n, INT_MAX);dist[src] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push({0, src});while (!pq.empty()) {int u = pq.top().second;int current_dist = pq.top().first;pq.pop();if (current_dist > dist[u]) {continue;}for (int v = 0; v < n; ++v) {if (delayMatrix[u][v] != -1 && u != v) {if (dist[v] > dist[u] + delayMatrix[u][v]) {dist[v] = dist[u] + delayMatrix[u][v];pq.push({dist[v], v});}}}}return dist;
}vector<int> findEscapeNodes(int n, const vector<vector<int>>& delayMatrix, const vector<int>& remainingCapacity, int faultyNode, int damagedCapacity) {vector<int> dist = dijkstra(delayMatrix, faultyNode, n);vector<pair<int, int>> candidates;for (int i = 0; i < n; ++i) {if (i != faultyNode && dist[i] != INT_MAX) {candidates.emplace_back(dist[i], i);}}sort(candidates.begin(), candidates.end(), [](const pair<int, int>& a, const pair<int, int>& b) {if (a.first != b.first) {return a.first < b.first;} else {return a.second < b.second;}});vector<int> escapeNodes;int totalCapacity = 0;for (const auto& candidate : candidates) {escapeNodes.push_back(candidate.second);totalCapacity += remainingCapacity[candidate.second];if (totalCapacity >= damagedCapacity) {break;}}if (totalCapacity < damagedCapacity) {escapeNodes.clear();for (int i = 0; i < n; ++i) {if (i != faultyNode) {escapeNodes.push_back(i);}}}return escapeNodes;
}int main() {int n;cin >> n;vector<vector<int>> delayMatrix(n, vector<int>(n));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cin >> delayMatrix[i][j];}}vector<int> remainingCapacity(n);for (int i = 0; i < n; ++i) {cin >> remainingCapacity[i];}int faultyNode;cin >> faultyNode;int damagedCapacity;cin >> damagedCapacity;vector<int> escapeNodes = findEscapeNodes(n, delayMatrix, remainingCapacity, faultyNode, damagedCapacity);for (size_t i = 0; i < escapeNodes.size(); ++i) {if (i != 0) {cout << " ";}cout << escapeNodes[i];}cout << endl;return 0;
}

代码解释

1. dijkstra 函数：
   • 计算从 src 节点到其他所有节点的最短时延。

   • 使用优先级队列（最小堆）优化 Dijkstra 算法。

2. findEscapeNodes 函数：
   • 调用 dijkstra 计算最短时延。

   • 筛选候选节点（排除 faultyNode 和不可达节点）。

   • 按时延和编号排序候选节点。

   • 贪心选择逃生节点集，直到剩余容量总和 ≥ damagedCapacity。

   • 如果容量不足，返回所有节点（排除 faultyNode）。

3. main 函数：
   • 读取输入数据。

   • 调用 findEscapeNodes 获取逃生节点列表。

   • 输出结果。

样例验证

输入：

4
-1 5 -1 8
5 -1 1 3
-1 1 -1 4
8 3 4 -1
10 20 15 25
2
12

执行流程：

1. dijkstra 计算节点 2 的最短时延：
   • dist = [5, 1, 0, 4]（节点 2 到其他节点的最短时延）。

2. 候选节点：[(1, 1), (4, 3), (5, 0)]（时延和编号）。

3. 排序后：[(1, 1), (4, 3), (5, 0)]。

4. 选择节点 1（剩余容量 20 ≥ 12），输出 1。

输出：

1

复杂度分析

• 时间复杂度：

• Dijkstra 算法：O(n^2)（邻接矩阵实现）。

• 排序候选节点：O(n log n)。

• 总复杂度：O(n^2)。

• 空间复杂度：

• dist 数组：O(n)。

• 候选节点列表：O(n)。

• 总复杂度：O(n)。

#include<bits/stdc++.h> 
using namespace std;int main(){int n;// 业务节点数cin>>n;vector<vector<int>>delayMatrix(n+1,vector<int>(n+1,-1));vector<int> remainingCapacity(n+1,0);for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>delayMatrix[i][j];}}for(int i=0;i<n;i++){cin>>remainingCapacity[i];}int faultyNode,num;cin>>faultyNode>>num;// 求单源最短路径const int inf=99999999;vector<int> d(n,inf);vector<bool> vis(n,false);d[faultyNode] = 0;for(int i=0;i<n;i++){int tmp=inf;int idx=-1;for(int j=0;j<n;j++){if(tmp>d[j]&&!vis[j]){idx=j;tmp=d[j];}}//if(idx!=-1)vis[idx]=true;else{break;}for(int v=0;v<n;v++){if(idx!=v&&delayMatrix[idx][v]!=-1&&delayMatrix[idx][v]+d[idx]<d[v]){d[v]=delayMatrix[idx][v]+d[idx];}}}// 计算vector<bool> selected(n+1,false);selected[faultyNode]=true;vector<pair<int,int>> q;for(int i=0;i<n;i++){if(i!=faultyNode&&d[i]!=inf) q.push_back({d[i],i});}sort(q.begin(),q.end());vector<int> ans;int size=q.size();for(int i=0;i<size;i++){num-=remainingCapacity[q[i].second];ans.push_back(q[i].second);if(num<=0)break;}for(auto&x:ans){cout<<x<<" ";}return 0;
}