11 • 4个月前
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 定义任务结构体
struct Task {
int time; // 任务所需时间
vector<int> prereq; // 任务的先决条件
};
int main() {
int n;
cin >> n;
vector<Task> tasks(n + 1); // 任务列表，索引从1到n
vector<int> indegree(n + 1); // 每个任务的入度
vector<int> completionTime(n + 1, 0); // 每个任务的完成时间
// 读取任务信息
for (int i = 1; i <= n; ++i) {
int taskNum, time;
cin >> taskNum >> time;
tasks[taskNum].time = time;
int prereq;
while (cin >> prereq && prereq != 0) {
tasks[taskNum].prereq.push_back(prereq);
indegree[taskNum]++;
}
}
queue<int> q;
// 找出所有入度为0的任务，即没有先决条件的任务
for (int i = 1; i <= n; ++i) {
if (indegree[i] == 0) {
q.push(i);
completionTime[i] = tasks[i].time; // 直接完成
}
}
// 拓扑排序
while (!q.empty()) {
int current = q.front();
q.pop();
// 遍历当前任务的后续任务
for (int i = 1; i <= n; ++i) {
if (find(tasks[i].prereq.begin(), tasks[i].prereq.end(), current) != tasks[i].prereq.end()) {
// 更新后续任务的完成时间
completionTime[i] = max(completionTime[i], completionTime[current] + tasks[i].time);
// 减少入度
indegree[i]--;
// 如果后续任务入度为0，则可以开始执行
if (indegree[i] == 0) {
q.push(i);
}
}
}
}
// 找出所有任务完成的最长时间
int totalTime = *max_element(completionTime.begin(), completionTime.end());
cout << totalTime << endl;
return 0;
}
评论:
#include<iostream>
#include<vector>
#include<queue>
#include<fstream>
using namespace std;
vector<int> map[100001];
int deg[100001]; //每个节点的入度
queue<int> Q; //放入每个已经入度为0的节点
int workTime[100001];
int startTime[100001];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int node;
cin >> node;
cin >> workTime[node];
int num;
for (cin >> num; num > 0; cin >> num) {
map[num].push_back(node);
deg[node]++;
}
if (deg[node] == 0) Q.push(node);
}
int ans = 0;
while (!Q.empty()) {
int node = Q.front(); Q.pop();
int endTime = startTime[node] + workTime[node];
ans = max(ans, endTime);
for (int value : map[node]) {
deg[value]--;
startTime[value] = max(startTime[value], endTime);
if (deg[value] == 0) Q.push(value); //我们只需要检查入度是否变为0即可
}
}
cout << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
vector<int> d[10005]; //d[i]中所有元素的前置任务是i (i是d[i]的前置任务)
int worktime[10005]; //存储每个任务所需时间
int starttime[10005]; //每个任务开始时间
int deg[10005]; //存储每个节点入度(deg[i]表示i任务有几个前置任务)
int ans; //存储最终结果
queue<int> q; //放入入度为0的节点(没有前置任务的任务)
int main(){
int n;
cin>>n;
for(int a=0;a<n;a++){
int node,num;
cin>>node;
cin>>worktime[node];
for(cin>>num;num!=0;cin>>num){
d[num].push_back(node); //表示num是node的前置任务
deg[node]++;
}
if(deg[node]==0){
q.push(node); //无前置，入队
}
}
//输入结束，开始处理数据
while(!q.empty()){
int node=q.front(); //此处node无前置任务，且是d[node]中所有元素的前置任务
q.pop();
int endtime=starttime[node]+worktime[node];
ans=max(ans,endtime);
for(int i=0;i<d[node].size();i++){
deg[d[node][i]]--; //此处node任务已完成,故d[node]数组中每个需完成的前置任务数量自减
starttime[d[node][i]]=max(starttime[d[node][i]],endtime);
if(deg[d[node][i]]==0) q.push(d[node][i]); //我们只需要检查入度是否变为0即可
}
}
cout<<ans<<endl;
return 0;
}
请先登录，才能进行评论