搜索

CF Diary V


发布时间: 2022-11-24 19:45:03    浏览次数:32 次

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;
}
免责声明 CF Diary V,资源类别:文本, 浏览次数:32 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 07:45:03。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/Prgl/p/16915876.html