CF Diary V - 暮无雪代码博客

11.22-
每 \(10\) 题一篇 \(\texttt{>o<}\) 。

E. Count Seconds

\(\texttt{*2200}\)

题意

一个 \(n\) 个节点 \(m(1\le n,m\le10000)\) 条边的 \(\texttt{DAG}\) ，仅有一个点没有出度，每个点有值 \(a_i(0\le a_i\le10^9)\) ，每秒钟值 \(\ge0\) 的点的权值会 \(-1\) ，其所指向的点的权值都会 \(+1\) 。求所有点的权值都为 \(0\) 时的最短时间， \(mod\ 998244353\) 。

题解

考虑拓扑排序，如果一个点一直向后流动，那么其清空的时间就是它所有前驱权值总和，但可能有的点不会一直流动，考虑直接模拟前 \(n\) 秒，由于最长链不超过 \(n\) ，所以所有点最后接收到的流在这之前一定抵达，也就是在 \(n\) 秒后所有点在彻底清空之前一定会不停向后流动，此时在按之前的做法做就可以了，复杂度 \(O(nm)\) 。

代码

view code

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<LL, LL>;
using TP = tuple<int, int, int>;
#define all(x) x.begin(),x.end()
#define mst(x,v) memset(x,v,sizeof(x))
#define mul(x,y) (1ll*(x)*(y)%mod)
#define mk make_pair
//#define int LL
//#define double LD
//#define lc p*2
//#define rc p*2+1
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const double pi = acos(-1);
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 100010;

LL T, N, M, A[1010], in[1010];
bool po[1010];
vector<int>G[1010];

void add_edge(int from, int to)
{
	G[from].push_back(to);
}

void solve()
{
	int F = 0;
	for (int i = 1; i <= N; i++)
	{
		if (!G[i].size())
		{
			F = i;
			break;
		}
	}
	for (int i = 1; i <= N + 5; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (A[j])
				break;
			if (j == N)
			{
				cout << i - 1 << endl;
				return;
			}
		}
		for (int v = 1; v <= N; v++)
		{
			if (A[v])
				po[v] = true;
			else
				po[v] = false;
		}
		for (int v = 1; v <= N; v++)
		{
			if (po[v])
			{
				for (auto& to : G[v])
					A[to]++;
				A[v]--;
			}
		}
	}
	queue<int>que;
	for (int i = 1; i <= N; i++)
	{
		if (!in[i])
			que.push(i);
	}
	while (!que.empty())
	{
		int v = que.front(); que.pop();
		for (auto& to : G[v])
		{
			in[to]--;
			if (!in[to])
				que.push(to);
			A[to] = (A[v] + A[to]) % mod;
		}
	}
	cout << (A[F] + N + 5) % mod << endl;
}

int main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		cin >> N >> M;
		for (int i = 1; i <= N; i++)
			cin >> A[i], G[i].clear(), in[i] = 0;
		int x, y;
		for (int i = 1; i <= M; i++)
			cin >> x >> y, add_edge(x, y), in[y]++;
		solve();
	}
	return 0;
}