current position:Home>E. Count Seconds (DAG/topological sort/tree dp)

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

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

题目
参考

题意

给定一个DAG,其中出度为0的结点只有一个.Each node has an initial valuea[i].每秒,The following things happen at each node:

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

Ask what time,所有结点的a值都为0.

顶点n和边数m
1<=n,m<=1000
答案对998244353取模.

思路

我们把aValues ​​replace descriptions with globs of water,更形象点.
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.
如果在n步后,There is also non0的a值,At this point each node can be calculatedu,How many times he will contribute to the sink.
在这里插入图片描述
例如,对于上图,汇点是5.那么

  • 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,关注下,一起快乐刷题吧~

copyright notice
author[Luo gkv],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/218/202208060918144503.html

Random recommended