?

?

11 · 发布于 2024-08-03 · 浏览 490 回复 2 
#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;
}

全部回复 共 2 条

  1. ------监狱栅栏------ #1 · 
    #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;
}
  2. 键盘敲碎夜深沉，代码如麻乱假真 #2 · 
    #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;
}

发表回复