【题目链接】
洛谷 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 <bits/stdc++.h>
using namespace std;
#define N 10005
vector<int> edge[N];
int n, degIn[N], len[N], fin[N], mxFin;//len[i]：任务i的完成时长 fin[i]：任务i最早的完成时间
void topoSort()
{
queue<int> 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 <bits/stdc++.h>
using namespace std;
#define N 10005
vector<int> edge[N];
int n, degIn[N], len[N], start[N], mxFin;//len[i]：任务i的完成时长 start[i]：任务i最早的开始时间
void topoSort()
{
queue<int> 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 <bits/stdc++.h>
using namespace std;
#define N 10005
vector<int> 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的准备工作，那么存在弧<t, f>
}
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 <bits/stdc++.h>
using namespace std;
#define N 10005
vector<int> 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的准备工作，那么存在弧<t, f>
}
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;
}
