#1175 : 拓扑排序·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho所在学校的校园网被黑客入侵并投放了病毒。这事在校内BBS上立刻引起了大家的讨论&＃xff0c;当然小Hi和小Ho也参与到了其中。从大家各自了解的情况中&＃xff0c;小Hi和小Ho整理得到了以下的信息&＃xff1a;
- 校园网主干是由N个节点(编号1..N)组成&＃xff0c;这些节点之间有一些单向的网路连接。若存在一条网路连接(u,v)链接了节点u和节点v&＃xff0c;则节点u可以向节点v发送信息&＃xff0c;但是节点v不能通过该链接向节点u发送信息。
- 在刚感染病毒时&＃xff0c;校园网立刻切断了一些网络链接&＃xff0c;恰好使得剩下网络连接不存在环&＃xff0c;避免了节点被反复感染。也就是说从节点i扩散出的病毒&＃xff0c;一定不会再回到节点i。
- 当1个病毒感染了节点后&＃xff0c;它并不会检查这个节点是否被感染&＃xff0c;而是直接将自身的拷贝向所有邻居节点发送&＃xff0c;它自身则会留在当前节点。所以一个节点有可能存在多个病毒。
- 现在已经知道黑客在一开始在K个节点上分别投放了一个病毒。
举个例子&＃xff0c;假设切断部分网络连接后学校网络如下图所示&＃xff0c;由4个节点和4条链接构成。最开始只有节点1上有病毒。
最开始节点1向节点2和节点3传送了病毒&＃xff0c;自身留有1个病毒&＃xff1a;
其中一个病毒到达节点2后&＃xff0c;向节点3传送了一个病毒。另一个到达节点3的病毒向节点4发送自己的拷贝&＃xff1a;
当从节点2传送到节点3的病毒到达之后&＃xff0c;该病毒又发送了一份自己的拷贝向节点4。此时节点3上留有2个病毒&＃xff1a;
最后每个节点上的病毒为&＃xff1a;
小Hi和小Ho根据目前的情况发现一段时间之后&＃xff0c;所有的节点病毒数量一定不会再发生变化。那么对于整个网络来说&＃xff0c;最后会有多少个病毒呢&＃xff1f;
提示&＃xff1a;拓扑排序的应用
输入
第1行&＃xff1a;3个整数N,M,K&＃xff0c;1≤K≤N≤100,000&＃xff0c;1≤M≤500,000
第2行&＃xff1a;K个整数A[i]&＃xff0c;A[i]表示黑客在节点A[i]上放了1个病毒。1≤A[i]≤N
第3..M&＃43;2行&＃xff1a;每行2个整数 u,v&＃xff0c;表示存在一条从节点u到节点v的网络链接。数据保证为无环图。1≤u,v≤N
输出
第1行&＃xff1a;1个整数&＃xff0c;表示最后整个网络的病毒数量 MOD 142857
样例输入-
4 4 1
1
1 2
1 3
2 3
3 4
样例输出-
6
#include
#include
#include
#include
#include
#include
#include
#include
#include #define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 100010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int Read()
{char c &＃61; getchar();while (c <&＃39;0&＃39; || c > &＃39;9&＃39;) c &＃61; getchar();int x &＃61; 0;while (c >&＃61; &＃39;0&＃39; && c <&＃61; &＃39;9&＃39;) {x &＃61; x * 10 &＃43; c - &＃39;0&＃39;;c &＃61; getchar();}return x;
}void Print(int a)
{if(a>9)Print(a/10);putchar(a%10&＃43;&＃39;0&＃39;);
}int n,m,k;
int a[MAXN];
vector vec[MAXN];
int rd[MAXN];
int vis[MAXN];void Topsort()
{int ans&＃61;0;queue que;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(vis[i]&&rd[i]&＃61;&＃61;0){que.push(i);}}while(!que.empty()){int u&＃61;que.front(); que.pop();
// ans&＃43;&＃61;a[u];
// ans%&＃61;142857;
// cout<<"u "<// cout<<"v "<// cout<<"i "<}int main()
{
// fread;while(scanf("%d%d%d",&n,&m,&k)!&＃61;EOF){MEM(a,0);for(int i&＃61;0;i}
京公网安备 11010802041100号