拓扑排序板子

什么是拓扑排序.大概就是给你一个有向无环图（DAG） 然后对他们进行一次线性排序，让所有的点按方向有序排序？.

比如A->B->D 这样，要做D就要先做B，要做B就要先做A...

bfs序拓扑排列：

1.找到入度为0的点加入队列

2.将队首取出，到达的点入度减一，如果某点入度变为0，将其加入队列.

3.出队，记录.

洛谷 P1113 杂物 板子题 

题目

1行：一个整数nn，必须完成的杂务的数目(3 \le n \le 10,0003≤n≤10,000)；

第22至(n+1)(n+1)行： 共有nn行，每行有一些用11个空格隔开的整数，分别表示：

* 工作序号(11至nn,在输入文件中是有序的)；

* 完成工作所需要的时间len(1 \le len \le 100)len(1≤len≤100)；

* 一些必须完成的准备工作，总数不超过100100个，由一个数字00结束。有些杂务没有需要准备的工作只描述一个单独的00，整个输入文件中不会出现多余的空格

思路：拓扑排序的同时开两个数组 一个是ans一个是work

然后转移方程是这个

	wktime[to]=max(wktime[to],wktime[x]+a[to]);

到达一个点的工作时间等于这个点本身工作时间和（如果有的话）前驱工作时间加上这个点的工作时间，取大的值.

为什么要这么做而不是直接更新取后面那个数字呢？因为一个点可能会被重复访问，重复访问时应该取最大的值.而不是被新的值取代.

洛谷p1113 杂物代码：

#include
#include
#include
#include
#define maxn 10005
using namespace std;
int wktime[maxn],in[maxn],a[maxn];
int main(){ int n,m,i,j,x,num,k,time,to;cin>>n;vector G[maxn];
queue Q;
for(i=1;i