時間限制:10000ms 單點時限:1000ms 內存限制:256MB

描述

Professor Q develops a new software. The software consists of N modules which are numbered from 1 to N. The i-th module will be started up by signal Si. If signal Si?is generated multiple times, the i-th module will also be started multiple times. Two different modules may be started up by the same signal. During its lifecircle, the i-th module will generate Ki?signals: E1, E2, ..., EKi. These signals may start up other modules and so on. Fortunately the software is so carefully designed that?there is no loop in the starting chain of modules, which means eventually all the modules will be stoped. Professor Q generates some initial signals and want to know how many times each module is started.

輸入

The first line contains an integer T, the number of test cases. T test cases follows.

For each test case, the first line contains contains two numbers N and M, indicating the number of modules and number of signals that Professor Q generates initially.

The second line contains M integers, indicating the signals that Professor Q generates initially.

Line 3~N + 2, each line describes an module, following the format S, K, E1, E2, ... , EK. S represents the signal that start up this module. K represents the total amount of signals that are generated during the lifecircle of this module. And E1?... EK?are these signals.

For 20% data, all N, M <= 10
For 40% data, all N, M <= 103
For 100% data, all 1 <= T <= 5, N, M <= 105, 0 <= K <= 3, 0 <= S, E <= 105.

Hint: HUGE input in this problem. Fast IO such as scanf and BufferedReader are recommended.

輸出

For each test case, output a line with N numbers Ans1, Ans2, ... , AnsN. Ansi?is the number of times that the i-th module is started. In case the answers may be too large, output the answers modulo 142857 (the remainder of division by 142857).

樣例輸入

3 3 2 123 256 123 2 456 256 456 3 666 111 256 256 1 90 3 1 100 100 2 200 200 200 1 300 200 0 5 1 1 1 2 2 3 2 2 3 4 3 2 4 5 4 2 5 6 5 2 6 7

樣例輸出

1 1 3 1 2 2 1 1 2 3 5

解題思路：這個題目的思路很簡單，建立好圖之后，DFS掃一遍就ok了。。。但看官方題解，這個算法還不是最優的，最優的是建立的圖之后進行拓撲排序。。。仔細想想確實是這樣的，只能說觀察不夠細致。。

解題思路

通過題意，我們首先可以確定，不同模塊之間可以按照以下原則構成一個有向無環圖：

• 初始信號流，即?M?個初始信號，我們將其設定為模塊0發出的信號
• 若模塊i發出的信號能夠使得模塊j被激活，我們連接一條從i到j的有向邊(i,j)

比如數據：

3 2 123 256 123 2 456 256 456 3 666 111 256 256 1 90

對應的圖為：

由于原題中給出的信號在0~10^5之間，因此我們可以用一個大小為10^5的數組signList來記錄信號可以激活的模塊，輔助我們構造整個圖：

Input n Input m // 將初始數據流做為 module 0 For i = 1 .. mInput signmodule[0].sendSign.push(sign) End For // 讀取其他module的信息 For i = 1 .. nInput signmodule[i].activeSign = signsignList[ sign ].canActiveModule.push(i)Input numFor j = 1 .. numInput signmodule[i]sendSign.push(sign)End For End For // 構造有向無環圖 For i = 0 .. nFor sign in module[i].sendSignFor j in signList[ sign ].canActiveModuleaddEdge(i, j)End ForEnd For End For

在得到有向無環圖之后，一個簡單的做法是直接在上面做一次DFS，去統計每個點被訪問到的次數：

DFS(nowModule):If (nowModule not 0) ThenactiveCount[ nowModule ] = activeCount[ nowModule ] + 1End IfFor each j in (nowModule, j)DFS(j)End For

該算法的時間復雜度非常高，但由于本題沒有設計專門針對的數據，所以在測試時也能通過所有的測試點。

但是顯然這不是我們要的最優算法，本題實際考察的算法為拓撲排序(toposort)。

利用拓撲排序，在O(n + m)的時間內計算出所有點被訪問的次數，具體的算法講解可以參見hiho一下第48期

在本題中，訪問次數對應的為第48期題目中的病毒數量。因此我們在構造完圖之后，可以使用同樣的算法來解決：

// 在構造圖時同時統計入度 For i = 0 .. nFor sign in module[i].sendSignFor j in signList[ sign ].canActiveModuleaddEdge(i, j)inDegree[j] = inDegree[j] + 1End ForEnd For End For// 進行拓撲排序 tail = 0; For i = 0 .. n // 這里一定要從0開始，因為Module 0也是圖中的點If (inDegree[i] == 0) Then // 入度為0的點sequence[tail] = itail = tail + 1End If End ForactiveCount[0] = 1 // 設定初始信號流的訪問次數為1 activeCount[1 .. n] = 0 i = 0 While (i < tail) ThennowModule = sequence[i]For each j in (nowModule, j)activeCount[j] = activeCount[j] + activeCount[ nowModule ]inDegree[j] = inDegree[j] - 1If (inDegree[j] == 0) Thensequence[tail] = jtail = tail + 1End IfEnd Fori = i + 1 End While

最后再將activeCount數組依次輸出即可。由于本題有多組數據，在實現時一定要注意初始化。

AC:

#include<cstdio> #include<cstring> using namespace std;const int maxn = 1e5+5; struct SOFTWARE {int start;int num;int E[5]; }sft[maxn];struct VERTEX {int startE;int first; }ver[maxn];struct Node {int id;int next; }list[maxn]; int n,m,sign[maxn],cnt,vis[maxn];void add(int e,int id) {ver[e].startE = e;list[cnt].id = id;if(ver[e].first == -1) ver[e].first = cnt++;else{list[cnt].next = ver[e].first;ver[e].first = cnt++;} }void init() {memset(vis,0,sizeof(vis));memset(list,-1,sizeof(list));memset(ver,-1,sizeof(ver));cnt = 0; }void dfs(int cur,int e) {if(ver[e].first == -1) return;for(int i = ver[e].first; i != -1; i = list[i].next){int k = list[i].id;vis[k]++;for(int j = 1; j <= sft[k].num; j++)dfs(k,sft[k].E[j]);} }int main() { int t;scanf("%d",&t);while(t--){init();scanf("%d%d",&n,&m);for(int i = 1; i <= m; i++)scanf("%d",&sign[i]);for(int i = 1; i <= n; i++){scanf("%d%d",&sft[i].start,&sft[i].num);add(sft[i].start,i);for(int j = 1; j <= sft[i].num; j++)scanf("%d",&sft[i].E[j]);}for(int i = 1; i <= m; i++)dfs(0,sign[i]);for(int i = 1; i <= n; i++)printf("%d ",vis[i]);printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的hihocoder #1136 : Professor Q's Software的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。