【题目链接】

洛谷 P1113 杂务

【题目考点】

1. 图论：拓扑排序

2. 动规：DAG图上动规

【解题思路】

首先对该问题进行抽象，每项杂务是一个顶点，如果杂务A是杂务B的准备工作，那么A到B有一条有向边。整个图是有向图。
设数组len，len[i]表示完成杂务i所需要的时长。

解法1：拓扑排序

写法1：设数组表示杂务的完成时刻

假设这个人在工作中不会休息，完成一项杂务后，会立刻去做下一项杂务。
设数组fin，fin[i]表示杂务i的完成时刻。

按照拓扑排序顺序，分别求每项杂务的完成时刻。
对于入度为0的顶点i，该杂务的完成时刻就是完成该杂务的时长len[i]。
每确定一项杂务u的完成时刻，就更新该顶点u的邻接点v的完成时刻。
已知u的完成时刻为fin[u]，v应该在u完成后再开始，这样的话v的完成时刻为fin[u]+len[v]。
对于v的每个准备工作u，都可以推出v的完成时刻为fin[u]+len[v]。而v必须在所有准备工作完成后才能开工，因此v的完成时刻fin[v]应该为所有求出的fin[u]+len[v]的最大值。即更新写法为:fin[v] = max(fin[v], fin[u]+len[v])

最后求出所有杂务完成时刻的最大值，即为完成所有任务需要的时间。

写法2：设数组表示杂务的开始时刻

另一种方法，可以设数组start，start[i]表示杂务i的开工时刻。在确定u的开工时刻start[u]后，确定u的邻接点v的开工时刻，写为：start[v] = max(start[v], start[u]+len[u])

最后求出所有杂务开始时刻加任务时长的最大值，即为完成所有任务需要的时间。

解法2：图上动规

题目中说：“杂务k的准备工作只可能在杂务1至k-1中。”即便没有这个条件，我们也可以先做拓扑排序，得到的序列一定满足序列中第i项工作的准备工作都在第1至第i-1项工作中。

既然有这一条件，就无需先做拓扑排序了。建图时，改为建反图，即如果杂务A是杂务B的准备工作，那么让B到A有一条有向边。
在这样的图中，一个顶点的邻接点就是它的准备工作。
设数组fin，fin[i]表示杂务i的完成时刻。
当按照给定序列顺序，需要求fin[u]时，由于u的准备工作v在序列中排在u的前面，所以此时一定已经求出了fin[v]，fin[v]是已知的。求所有u的准备工作的结束时间的最大值，即为u的开始时刻，再加上完成u的时间len[u]，就得到了完成u的最早时刻fin[u]。
同理，也可以设任务的开始时刻来完成该题。

【题解代码】

解法1：拓扑排序

• 写法1：设数组表示杂务的完成时刻

#include 
using namespace std;
#define N 10005
vector edge[N];
int n, degIn[N], len[N], fin[N], mxFin;//len[i]：任务i的完成时长 fin[i]：任务i最早的完成时间 
void topoSort()
{queue que;for(int v = 1; v <= n; ++v)if(degIn[v] == 0){que.push(v);fin[v] = len[v];}while(que.empty() == false){int u = que.front();que.pop();for(int v : edge[u]){fin[v] = max(fin[v], fin[u]+len[v]);if(--degIn[v] == 0)que.push(v);}}
}
int main()
{int a, t;cin >> n;for(int f = 1; f <= n; ++f){cin >> a >> len[f];while(cin >> t && t != 0){edge[t].push_back(f);degIn[f]++;}}topoSort();for(int v = 1; v <= n; ++v)mxFin = max(mxFin, fin[v]);cout << mxFin;return 0;
}

• 写法2：设数组表示杂务的开始时刻

#include 
using namespace std;
#define N 10005
vector edge[N];
int n, degIn[N], len[N], start[N], mxFin;//len[i]：任务i的完成时长 start[i]：任务i最早的开始时间 
void topoSort()
{queue que;for(int v = 1; v <= n; ++v)if(degIn[v] == 0)que.push(v);while(que.empty() == false){int u = que.front();que.pop();for(int v : edge[u]){start[v] = max(start[v], start[u]+len[u]);if(--degIn[v] == 0)que.push(v);}}
}
int main()
{int a, t;cin >> n;for(int i = 1; i <= n; ++i){cin >> a >> len[i];while(cin >> t && t != 0){edge[t].push_back(i);degIn[i]++;}}topoSort();for(int v = 1; v <= n; ++v)mxFin = max(mxFin, start[v]+len[v]);cout << mxFin;return 0;
}

解法2：图上动规

• 写法1：设数组表示杂务的完成时刻

#include 
using namespace std;
#define N 10005
vector edge[N];
int n, len[N], fin[N], mxFin;//len[i]：任务i的完成时长 fin[i]：任务i最早的开始时间 
int main()
{int a, t;cin >> n;for(int f = 1; f <= n; ++f){cin >> a >> len[f];fin[f] = len[f];//先将每个任务的结束时间设为完成时长 while(cin >> t && t != 0)edge[t].push_back(f);//如果f是t的准备工作，那么存在弧 }for(int u = 1; u <= n; ++u)for(int v : edge[u])//找所有u的准备工作fin[v] = max(fin[v], fin[u]+len[v]);for(int v = 1; v <= n; ++v)mxFin = max(mxFin, fin[v]);cout << mxFin;return 0;
}

• 写法2：设数组表示杂务的开始时刻

#include 
using namespace std;
#define N 10005
vector edge[N];
int n, len[N], start[N], mxFin;//len[i]：任务i的完成时长 start[i]：任务i最早的开始时间 
int main()
{int a, t;cin >> n;for(int f = 1; f <= n; ++f){cin >> a >> len[f];while(cin >> t && t != 0)edge[t].push_back(f);//如果f是t的准备工作，那么存在弧 }for(int u = 1; u <= n; ++u)for(int v : edge[u])//找所有u的准备工作start[v] = max(start[v], start[u]+len[u]);for(int v = 1; v <= n; ++v)mxFin = max(mxFin, start[v]+len[v]);cout << mxFin;return 0;
}