题目1 : 拓扑排序·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho所在学校的校园网被黑客入侵并投放了病毒。这事在校内BBS上立刻引起了大家的讨论，当然小Hi和小Ho也参与到了其中。从大家各自了解的情况中，小Hi和小Ho整理得到了以下的信息：
- 校园网主干是由N个节点(编号1..N)组成，这些节点之间有一些单向的网路连接。若存在一条网路连接(u,v)链接了节点u和节点v，则节点u可以向节点v发送信息，但是节点v不能通过该链接向节点u发送信息。
- 在刚感染病毒时，校园网立刻切断了一些网络链接，恰好使得剩下网络连接不存在环，避免了节点被反复感染。也就是说从节点i扩散出的病毒，一定不会再回到节点i。
- 当1个病毒感染了节点后，它并不会检查这个节点是否被感染，而是直接将自身的拷贝向所有邻居节点发送，它自身则会留在当前节点。所以一个节点有可能存在多个病毒。
- 现在已经知道黑客在一开始在K个节点上分别投放了一个病毒。
举个例子，假设切断部分网络连接后学校网络如下图所示，由4个节点和4条链接构成。最开始只有节点1上有病毒。
最开始节点1向节点2和节点3传送了病毒，自身留有1个病毒：
其中一个病毒到达节点2后，向节点3传送了一个病毒。另一个到达节点3的病毒向节点4发送自己的拷贝：
当从节点2传送到节点3的病毒到达之后，该病毒又发送了一份自己的拷贝向节点4。此时节点3上留有2个病毒：
最后每个节点上的病毒为：
小Hi和小Ho根据目前的情况发现一段时间之后，所有的节点病毒数量一定不会再发生变化。那么对于整个网络来说，最后会有多少个病毒呢？
输入
第1行：3个整数N,M,K，1≤K≤N≤100,000，1≤M≤500,000
第2行：K个整数A[i]，A[i]表示黑客在节点A[i]上放了1个病毒。1≤A[i]≤N
第3..M+2行：每行2个整数 u,v，表示存在一条从节点u到节点v的网络链接。数据保证为无环图。1≤u,v≤N
输出
第1行：1个整数，表示最后整个网络的病毒数量 MOD 142857
- 样例输入
-
4 4 1 1 1 2 1 3 2 3 3 4
- 样例输出
-
6
算法分析：这是一道拓扑排序的应用题目，因为数据量很大。所以dfs暴搜必然超时，仔细思考可知可以用拓扑排序来做。
思路是：设置一个cnt[]数组，cnt[i]表示:i节点有cnt[i]个病毒。假设当前访问的节点的是cur，cur节点有cnt[cur]
个病毒，我们将该点从图中移除前，将该点的病毒全部复制一次到它指向的节点。如图：
这里注意下：每次在计算某个节点有多少个病毒时，计算的过程中就采取取余的操作，因为点的数量很大，不断的累加会类型溢出。
还有一个地方需要注意，我用我之前的常规的拓扑排序的方式去写拓扑排序，每次都要进行in[]（入度数组）的遍历循环，找到某
一个入度为0的节点再进行移除操作，每次都要遍历确实很费时间。这样写我提交代码后TLE，得了70分。大致看来算法的过程是对
的了，只是时间上需要优化。于是我想到，既然每次找入度为0的节点都要去遍历数组，那么不去遍历就会节省时间。于是我想到了
可以用一个队列来保存目前图中所有入度为0的节点，每次取出一个来进行操作就行了，果断AC了。
代码：#include <stdio.h> #include <string.h> #include <stdlib.h> #include <ctype.h> #include <math.h> #include <iostream> #include <string> #include <stack> #include <vector> #include <set> #include <queue> #include <algorithm> #define N 100000+10 //最大节点数 #define M 500000+10 //最大的边数 #define MOD 142857 using namespace std; int n, m, k; int cnt[N]; //记录每个节点的病毒数量 int edgecnt; // int head[N]={0}; //头节点数组和节点数一样大 int p[M]; //指向数组和边数一样大 int Next[M]={0}; //模拟指针，初始化为0 int in[N]; void addedge(int u, int v) { ++edgecnt; p[edgecnt]=v; //当前这条边的指向是v Next[edgecnt]=head[u]; head[u]=edgecnt; } int topsort_cal() { queue<int>q;while(!q.empty()) q.pop(); int i, j; int ans=0; for(i=1; i<=n; i++)//秩序要遍历一次in[] 初始化一下队列 if(in[i]==0) q.push(i); int cur; while(!q.empty()) //队列不为空就还有入度为0的节点 { cur=q.front(); q.pop(); //别忘了出队列 ans = (ans%MOD + cnt[cur]%MOD)%MOD; in[cur]--; for(j=head[cur]; j; j=Next[j]) { in[p[j]]--; if(in[p[j]]==0)//删除了指向该点的一条边 判断该点现在是不是入度为0？ q.push(p[j]); //如果是则进队列 cnt[p[j]]=( cnt[p[j]]%MOD + cnt[cur]%MOD )%MOD;//如果此处不进行取余的操作 //到后面就会溢出 } } return ans; } int main() { int i, j; scanf("%d %d %d", &n, &m, &k); memset(cnt, 0, sizeof(cnt)); int dd; for(i=0; i<k; i++){ scanf("%d", &dd); cnt[dd]++; //放置病毒 } int u, v; edgecnt=0; memset(in, 0, sizeof(in)); //入度数组清空 for(i=0; i<m; i++) { scanf("%d %d", &u, &v); addedge(u, v); //建立单向边 in[v]++; } int ans=topsort_cal(); printf("%d ", ans ); return 0; }