雜物_洛谷1113_拓撲排序

題目描述

John的農場在給奶牛擠奶前有很多雜務要完成，每一項雜務都需要一定的時間來完成它。比如：他們要将奶牛集合起來，将他們趕進牛棚，為奶牛清洗乳房以及一些其它工作。盡早将所有雜務完成是必要的，因為這樣才有更多時間擠出更多的牛奶。當然，有些雜務必須在另一些雜務完成的情況下才能進行。比如：隻有将奶牛趕進牛棚才能開始為它清洗乳房，還有在未給奶牛清洗乳房之前不能擠奶。我們把這些工作稱為完成本項工作的準備工作。至少有一項雜務不要求有準備工作，這個可以最早着手完成的工作，标記為雜務1。John有需要完成的n個雜務的清單，并且這份清單是有一定順序的，雜務k(k>1)的準備工作隻可能在雜務1..k-1中。

寫一個程式從1到n讀入每個雜務的工作說明。計算出所有雜務都被完成的最短時間。當然互相沒有關系的雜務可以同時工作，并且，你可以假定John的農場有足夠多的勞工來同時完成任意多項任務。

輸入格式：

第1行：一個整數n，必須完成的雜務的數目(3<=n<=10,000)；

第2 ~ n+1行： 共有n行，每行有一些用1個空格隔開的整數，分别表示：

工作序号(1..n,在輸入檔案中是有序的)；

完成工作所需要的時間len（1<=len<=100）；

一些必須完成的準備工作，總數不超過100個，由一個數字0結束。有些雜務沒有需要準備的工作隻描述一個單獨的0，整個輸入檔案中不會出現多餘的空格。

輸出格式：

一個整數，表示完成所有雜務所需的最短時間。

題解

傻逼題，拓撲排然後對于每個點顯然最早完成時間就是所有前提完成的最晚時間+本身耗時

最後要在所有答案中找最大值

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#define debug puts("-----")
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define fill(x, t) memset(x, t, sizeof(x))
#define min(x, y) x<y?x:y
#define max(x, y) x>y?x:y
#define PI (acos(-1.0))
#define EPS (1e-8)
#define INF (1<<30)
#define ll long long
#define db double
#define ld long double
#define N 10001
#define E N * 201 + 1
#define MOD 100000007
#define L 255
using namespace std;
struct edge{int x, y, w, next;}e[E];
int ind[N], len[N], ls[N], t[N];
int edgeCnt;
inline int read(){
    int x = , v = ;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-'){
            v = -;
        }
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0'){
        x = (x << ) + (x << ) + ch - '0';
        ch = getchar();
    }
    return x * v;
}
inline int addEdge(int &cnt, const int &x, const int &y, const int &w = ){
    e[++ cnt] = (edge){x, y, w, ls[x]}; ls[x] = cnt;
    ind[y] += ;
    return ;
}
inline int topSort(const int &st){
    queue<int>q;
    q.push(st);
    while (!q.empty()){
        int now = q.front(); q.pop();
        for (int i = ls[now]; i; i = e[i].next){
            t[e[i].y] = max(t[e[i].y], t[now] + len[now]);
            if (! -- ind[e[i].y]){
                q.push(e[i].y);
            }
        }
    }
}
int main(void){
    int n = read();
    rep(i, , n){
        int now = read();
        len[i] = read();
        while (int pre = read()){
            addEdge(edgeCnt, pre, now);
        }
    }
    int st = ;
    rep(i, , n){
        if (!ind[i]){
            st = i;
        }
    }
    topSort(st);
    int ans = ;
    rep(i, , n){
        ans = max(ans, t[i] + len[i]);
    }
    printf("%d\n", ans);
    return ;
}