P1113 杂务

一眼拓扑排序。

但是发现可以同时做多件杂务，这就需要我们考虑好每件杂务的完成时间。显然，一件杂务要开始做，一定是该杂务的准备都完成，所以开始时间应该选择准备中最晚的完成时间。

怎么处理这个时间？

考虑一件杂务的“入度”是怎么变成 \(0\) 的，显然是队列中靠前的准备杂务到后面的准备杂务不断减小入度。我们考虑把完成时间晚的入度放到后面，这样当入度为 \(0\) 时，最后一个更新的一定是“准备中最晚的完成时间”，用这个时间来更新当前杂务。

至于怎么维护，用一个小根堆维护即可。

小 trick：准备工作是 \(1\sim k-1\) 的，于是可以直接从前到后转移。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second

typedef std::pair<int,int> pii;

template<typename T>
void read(T &x){
	 int f=1;
	 char c=getchar();
	 x=0;
	 while(c<'0'||c>'9'){
		 if(c=='-') f=-1;
		 c=getchar();
	 }
	 while(c>='0'&&c<='9') x=x*10+(int)(c-'0'),c=getchar();
	 x*=f;
}

template<typename T,typename I>
void chkmin(T &a,I b){
	 a=std::min(a,b);
}

template<typename T,typename I>
void chkmax(T &a,I b){
	a=std::max(a,b);
}

const int inf=1e18+10,MOD1=998244353,MOD2=1e9+7;

const int maxn=1e4+10;

std::vector<int>a[maxn],c[maxn];

int rd[maxn],len[maxn],st[maxn];

pii p[maxn];

signed main(){
	int n;
	read(n);
	memset(st,0x3f,sizeof(st));
	for(int i=1;i<=n;i++){
		read(i);
		read(len[i]);
		int x;
		read(x);
		while(x){
			c[x].push_back(i);
			rd[i]++;
			read(x);
		}
	}
	std::priority_queue<pii,std::vector<pii>,std::greater<pii> >q;
	for(int i=1;i<=n;i++)
		if(rd[i]==0){
			q.push({len[i],i});
			st[i]=len[i];
		}
	int ans=-inf;
	while(q.size()){
		int x=q.top().se;
		q.pop();
		for(int v:c[x]){
			rd[v]--;
			if(rd[v]==0) st[v]=st[x]+len[v],q.push({st[v],v});
		}
		if(c[x].size()==0) chkmax(ans,st[x]);
	}
	printf("%lld",ans);
	return 0;
}
/*
-读入字符一定检查回车
- 能不能搜索？
-函数要有返回值！
-想好了再写！
*/