# E. Count Seconds (DAG/topological sort/tree dp)

2022-08-06 09:23:48Luo gkv

## 题意

• 对于当前结点u,他的值a[u]会减一.
• 对于所有与v相连的结点,他的值a[v]会加一.

1<=n,m<=1000

## 思路

We focus on meeting points,即出度为0的点.所有的结点,will eventually pass through this meeting point.
Follow any nodeu,and its initial valuea[u],结点从uGo to the meeting point,最多需要n步,因为总共就n个结点.那么经过n步后,All from the beginningu出发的“水珠”,Must be connected to the meeting point.这些“水珠”流完,Currently only when the last glob has disappeared from the sink.

We are going to simulate nown步,如果在nstep range,所有结点的a值都为0,get the answer directly.

• From the sink itself to the sink,path only1条,The number of contributions is1
• 从2,4走到5的path only1条,So their contribution times are 1.
• 从3走到5,路径有2条,So its contribution count is 2
• 从1走到5,路径有3条,So its contribution count is 3.

How to find the number of contributions of each node？You can use topological sort,反向建图,从汇点开始,Count the number of paths from the sink to each node.

After calculating the number of contributions,The contribution of each node is a[i]*贡献次数.

Also pay attention to the modulo operation.

## 代码

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1010;
const int mod = 998244353;

int n, m, x, y;
ll a[maxn];
vector<int> g[maxn], rg[maxn];
ll d[maxn], tmp[maxn], sum[maxn];
queue<int> q;
void step() {
// Simulate walking1步
for (int i = 1; i <= n; ++i) {

tmp[i] = a[i];
a[i] = 0;
}
for (int i = 1; i <= n; ++i) {

if (!tmp[i]) {

continue;
}
a[i] += tmp[i] - 1;
for (auto v: g[i]) {

++a[v];
}
}
for (int i = 1; i <= n; ++i) {

if (a[i] >= mod) {
// 这里+mod,是因为前面有 tmp[i] - 1,Prevents arithmetic from being negative
a[i] = a[i] % mod + mod;
} else {

a[i] = a[i] % mod;
}
}
}
int cal() {
// 暴力 Simulate walkingn轮
for (int run = 1; run <= n; ++run) {

bool zero = true;
for (int i = 1; i <= n; ++i) {

if (a[i]) {

zero = false;
break;
}
}
if (zero) {
// All nodes are completed
return run - 1;
}
step();
}
return n;
}
void solve() {

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {

scanf("%lld", &a[i]);
g[i].clear();
rg[i].clear();
d[i] = 0;
sum[i] = 0;
}
for (int i = 1; i <= m; ++i) {

scanf("%d%d", &x, &y);
g[x].push_back(y);// 建图
rg[y].push_back(x);// 反向建图
++d[x];// 结点的出度,Corresponding to the reverse diagram 结点的入度
}
int res = cal();
if (res < n) {

printf("%d\n", res);
return;
}

// topu sort
while (!q.empty()) {

q.pop();
}
// Find the meeting point
for (int i = 1; i <= n; ++i) {

if (!d[i]) {

sum[i] = 1;
q.push(i);
// break;
}
}
while (!q.empty()) {
// 拓扑排序,Count the number of contributions for each node
int u = q.front();
q.pop();
sum[u] %= mod;// 注意取模
for (auto v: rg[u]) {

sum[v] += sum[u];
if (--d[v] == 0) {

q.push(v);
}
}
}
ll ans = n;// 计算ans 注意取模
for (int i = 1; i <= n; ++i) {

ll tmp = sum[i] * a[i] % mod;
ans = (ans + tmp) % mod;
}
printf("%lld\n", ans);
}
int main() {

int t;
scanf("%d", &t);
while (t--) {

solve();
}
return 0;
}
``````

## 最后

weixin gongzhonghao搜 对方正在debug,关注下,一起快乐刷题吧~