小明是一个做事很有规划的人。他列了 n 件在暑假期间要做的很多事情,编号分别为 1~n,对于每一件事情他都标注了优先级和必要程度,其中优先级从 1 到 9,必要程度从 1 到 5(数值越大,对应的优先级或者程度越高)。他希望对这些事情进行排序,排序规则如下: 必要程度大的事情排在前面;如果两件事情的必要程度一样则优先级大的排在前面;如果必要程度和优先级都一样则保持初始顺序不变。 但是小明发现,有些事情是有先后顺序的,比如说他要先学习数据结构才能学习算法,那么他就不能把算法排在数据结构的前面。所以他还给每一件事情标注了它的前置条件,即需要在它之前完成的事情。如果一个事情没有前置条件,就用 0 表示。 小明想知道,在满足所有前置条件的情况下,他能否按照排序规则来完成所有的事情。如果能,就输出排序后所有事情的初始编号,两个编号之间用空格隔开;如果不能,就输出 -1。 输出描述: 输出按照要求排序后所有事情的初始编号,两个编号之间用空格隔开。如果不能满足所有前置条件,就输出 -1。 输入例子: 3 9 3 0 1 4 0 5 2 1 输出例子:2 3 1。
时间: 2024-03-03 16:50:32 浏览: 34
这道题可以使用拓扑排序来解决。先将有前置条件的任务连边,然后进行拓扑排序。如果存在环,则说明无法完成所有任务;否则,按照拓扑序输出所有任务即可。
具体的思路是:首先统计每个任务的入度,然后将所有入度为 0 的任务加入队列,不断从队列中取出一个任务,将其指向的任务的入度减 1,如果减为 0,则将该任务加入队列中。最后如果队列中取出的任务数不等于任务总数,则说明存在环;否则,按照拓扑序输出所有任务即可。
以下是C++代码实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n;
vector<int> in_degree(n + 1); // 每个任务的入度
vector<int> priority(n + 1); // 每个任务的优先级
vector<int> necessary(n + 1); // 每个任务的必要程度
vector<vector<int>> adj(n + 1); // 每个任务指向的任务
for (int i = 1; i <= n; i++) {
string name;
cin >> name >> necessary[i] >> priority[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
string t1, t2;
cin >> t1 >> t2;
int u = stoi(t1.substr(1));
int v = stoi(t2.substr(1));
adj[u].push_back(v); // u 指向 v
in_degree[v]++; // v 的入度加 1
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
q.push(i);
}
}
vector<int> ans;
while (!q.empty()) {
int u = q.front();
q.pop();
ans.push_back(u);
for (int v : adj[u]) {
in_degree[v]--;
if (in_degree[v] == 0) {
q.push(v);
}
}
}
if (ans.size() != n) {
cout << -1 << endl;
} else {
sort(ans.begin(), ans.end(), [&](int x, int y) {
if (necessary[x] != necessary[y]) {
return necessary[x] > necessary[y];
} else if (priority[x] != priority[y]) {
return priority[x] > priority[y];
} else {
return x < y;
}
});
for (int x : ans) {
cout << x << " ";
}
cout << endl;
}
return 0;
}
```
希望能够帮到你!
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)