题目链接

解题思路

首先，我采用反向建边的方式建一DAG图，然后跑DFS（其实就是反的拓扑序），记忆化搜索，算出$f[i]$，即完成任务$i$所需的最短时间.

详细代码

#define USEFASTERREAD 1

#define rg register
#define inl inline
#define DEBUG printf("[Passing [%s] in line %d.]n", __func__, __LINE__)
#define putline putchar('n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
#include<cstdio>
#define rs freopen("test.in", "r", stdin), freopen("test.out", "w", stdout)

#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
struct IO
{
	void RS() {rs;} 
	template<typename T> inline IO r(T& x)const
	{
	    x = 0; T f = 1; char ch = getchar();
	    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
	    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');
	    x *= f; return *this;
	}
	template<typename T> inline IO w(T x)const
	{
	    if(x < 0) {putchar('-'); x = -x;}
	    if(x >= 10) w(x / 10);
	    putchar(x % 10 + '0'); return *this;
	}
	template<typename T> inline IO wl(const T& x)const {w(x), putline; return *this;}
	template<typename T> inline IO ws(const T& x)const {w(x), putsp; return *this;}
	inline IO l() {putline; return *this;}
	inline IO s() {putline; return *this;}
}io;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}

const int INF = 0x7f7f7f7f; 
const int MAXN = 10005;
const int MAXM = 10000005;
int n, len[MAXN];
struct Edge
{
	int v, nxt;
}e[MAXM];
int cnt, head[MAXN];
void addedge(int u, int v)
{
	e[++cnt].v = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
int f[MAXN];//任务的最早结束时间 
void dp(int u)
{
	if(f[u]) return;
	f[u] = len[u];
	int maxt = 0;
	for(rg int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		dp(v);
		maxt = Max(maxt, f[v]);//找到最晚结束的那个任务 
	}
	f[u] += maxt;
}
int main()
{
    //io.RS();
    io.r(n);
    for(rg int i = 1; i <= n; i++)
    {
		int u = 0;
		io.r(u);
		io.r(len[u]);
		int v = 1;
		io.r(v);
		while(v)
		{
			addedge(u, v);
			io.r(v);
		}
	}
	for(rg int i = 1; i <= n; i++)
		if(!f[i]) dp(i);
	int mint = -INF;
	for(rg int i = 1; i <= n; i++)
		mint = Max(mint, f[i]);
	io.wl(mint);
    return 0;
}

最后

以上就是闪闪哈密瓜为你收集整理的LGOJ P1113 杂务 解题报告题目链接解题思路详细代码的全部内容，希望文章能够帮你解决LGOJ P1113 杂务 解题报告题目链接解题思路详细代码所遇到的程序开发问题。

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