洛谷 P1113 杂务 简单拓扑排序

洛谷 P1113 杂务 简单拓扑排序

题解：

基本就是一道拓扑排序裸题。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<map>
#define MAX 10005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

//in记录每个点的入度，ti记录每个任务完成需要的时间，fi记录每个任务完成的最终时间
//最后我们要在fi中输出最大的一个
int in[MAX],ti[MAX],fi[MAX];
int n;
vector<int> adj[MAX];//邻接表

void topo(){
    int maxl=-1;
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            q.push(i);
            fi[i]=ti[i];
        }
    }
    while(!q.empty()){
        int top=q.front();
        q.pop();
        for(int i=0;i<adj[top].size();i++){
            int id=adj[top][i];
            in[id]--;
            if(in[id]==0){
                q.push(id);
            }
            //因为第id个任务的完成时间一定是它前面的任务中完成最晚的时间再加上自己完成的时间
            fi[id]=max(fi[id],fi[top]+ti[id]);
        }
    }
    for(int i=1;i<=n;i++){//取fi中最大的一个
        maxl=max(maxl,fi[i]);
    }
    printf("%d",maxl);
}

int main(){
    scanf("%d",&n);
    int a,len,b;
    for(int i=0;i<n;i++){
        scanf("%d%d",&a,&len);
        ti[a]=len;
        scanf("%d",&b);
        while(b!=0){
            in[a]++;//入度+1
            adj[b].push_back(a);
            scanf("%d",&b);
        }
    }
    topo();
    return 0;
}

最后

以上就是感性金鱼为你收集整理的洛谷 P1113 杂务 简单拓扑排序的全部内容，希望文章能够帮你解决洛谷 P1113 杂务 简单拓扑排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。