题解

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,timee[100001],rd[1000001],e[1000001];	//rd存每个点，e[i]存到第i个节点时用的时间 
vector <int> d[100001];						//存每个节点的孩子(对于d[i]中存储的是做完i才能做的任务)
queue <int> q;
int main()
{
	cin >> n;
	for (int i=1;i<=n;i++){
		int x;
		cin >> x >> timee[i];
		cin >> x;
		while(x!=0){
			d[x].push_back(i);				
			rd[i]++;						//节点入度+1 
			cin >> x;
		}
	}
	
//	for (int i=1;i<=n;i++){					//调试代码…… 
//		int sz=d[i].size();
//		cout << i << ": ";
//		for (int j=0;j<sz;j++){
//			cout << d[i][j] << " ";
//		}
//		cout << endl;
//	}
//	
//	for (int i=1;i<=n;i++){
//		cout << i << " ： "  << rd[i] << endl; 
//	}
		
	for (int i=1;i<=n;i++){					//找出没有前置任务的任务 
		if (rd[i]==0)q.push(i);
	}
	int ans=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		e[u]+=timee[u];						//e[i]加上该任务所用的时间 
		ans=max(e[u],ans);
		int sz=d[u].size();
		for (int i=0;i<sz;i++){	
			rd[d[u][i]]--;	
			e[d[u][i]]=max(e[d[u][i]],e[u]);		//因为一个节点可能被多次（多个父亲）遍历到，所以要去max 
			if (rd[d[u][i]]==0)q.push(d[u][i]);	
		}	
	}
	cout << ans;							//输出 
 }

题意

难道还有人不看题目就看题解吧

思路

推荐使用邻接表,不建议使用链式前向星

$e$数组用于存储从起点到这一步的时间

与这道题的题解代码的输入部分的区别在于 需要反向建边(因为要先完成那个再完成这个)

所以存储需要改动

代码

#include<iostream>
#include<vector>
#include<queue>
#define N 11451
using namespace std;
int n,ans=0;
vector<int>g[N];//邻接表
int ing[N];//记录每个点的入度
int len[N];//存储每个点的时间
int e[N];//记录每个点到起点的所需时间
queue<int>q;
void topo()//拓扑排序
{
    for(int i=1;i<=n;i++)
        if(ing[i]==0)//找出入度为0的点
            q.push(i);//入队
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        e[u]+=len[u];//总时间
        ans=max(e[u],ans);//取最大的,可能会多次遍历,看看能不能获取到更大的时长
        for(int i=0;i<(int)g[u].size();i++)
        {
            int v=g[u][i];
            ing[v]--;//减少一个入度
            e[v]=max(e[v],e[u]);//取最大的,可能会多次遍历,看看能不能获取到更大的时长
            if(ing[v]==0)//判断入度是否符合条件
            {
                q.push(v);//入队
            }
        }
    }
}
int main()
{
    cin>>n;//输入
    for(int i=1;i<=n;i++)
    {
        int s,t,x;
        cin>>s>>t>>x;//输入
        len[s]=t;//记录所需的时间
        while(x!=0)//为0结束
        {
            ing[s]++;//注意是哪个点
            g[x].push_back(s);//需要反向建边,因为要先完成那个再完成这个
            cin>>x;//逐个输入
        }
    }
    topo();//拓扑排序
    cout<<ans;//输出
    return 0;//完结散花
}

参考与鸣谢

@

#include <bits/stdc++.h>
#define ll longlong
#define INF 0x3f3f3f3f
#define maxn 110
#define N 2100
using namespace std;
int n,in[114514],a,b,ti[114514],ans,e[114514];
vector<int>v[114514];
int main(){
	for(int i=0;i<114514;i++)v[i].clear();
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a>>b;
		ti[a]=b;
		cin>>b;
		while(b!=0){
			v[b].push_back(a);
			in[a]++;
			cin>>b;
		}
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	vector<int>d;
	while(!q.empty()){
		int u=q.front();q.pop();
		e[u]+=ti[u];
		ans=max(e[u],ans);
		for(int i=0;i<v[u].size();i++){
			in[v[u][i]]--;
			e[v[u][i]]=max(e[v[u][i]],e[u]);
			if(in[v[u][i]]==0){
				q.push(v[u][i]);
			}
		}
    }
    cout<<ans;
}