Luogu P1113 杂务

我真的不知道为什么这题是图论题……
因为第\(n\)件事的前驱只会在前\(n-1\)件事中，所以可以从第\(1\)件事开始遍历。
而且，最优的情况便是第\(i\)件事的结束时间尽量大（第\(1\)件事的结束时间就是第\(1\)件事的花费时间），就选择第\(i\)件事作为第\(n\)件事的前驱。
得到每件事的结束时间后，与\(ans\)取max即可。（注意这题是让我们求时间的最小值，但要用max取答案，思维容易走进误区）

#include<bits/stdc++.h>
#define N 50010

using namespace std;

int n,ans;

struct node {
    int time,finish,cnt;
    int pre[110];
}event[N];

void Read() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int id,preevent;
        scanf("%d%d",&id,&event[i].time);
        while(scanf("%d",&preevent)&&preevent!=0) {
            event[i].pre[++event[i].cnt]=preevent;
        }
    }
    return;
}

void Solve() {
    event[1].finish=event[1].time;
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=event[i].cnt;j++) {
            event[i].finish=max(event[i].finish,event[event[i].pre[j]].finish+event[i].time);
        }
        ans=max(ans,event[i].finish);
    }
    printf("%d",ans);
    return;
}

int main()
{
    Read();
    Solve();
    return 0;
}

Luogu P1113 杂务

原文：https://www.cnblogs.com/luoshui-tianyi/p/11520926.html