CF1704E Count Seconds 题解

link 本题为原T2

⑨ 有一个 DAG，它有 $n$ 个节点和 $m$ 条边。该图恰好有一个节点没有出边。第 $i$ 个节点上有一个整数 $a_i$。

每秒钟发生以下情况：

• 设 $S$ 为有 $a_x>0$ 的节点集合 $x$。

• 对于所有 $x\in S$，从 $a_x$ 中减去 $1$，然后对于每个节点 $y$，如果存在从 $x$ 到 $y$ 的边，则向 $a_y$ 中添加 $1$。

找到所有 $a_i$ 变为 $0$ 的第一个时刻。答案对 $998244353$ 取模。

多测。$T\leq 1000$。$1\leq n,m\leq 1000$，$0\leq a_i\leq 10^9$。$\sum n,\sum m \leq 10,000$。

---

乍一看这道题似乎可以通过记录每个点最晚流出的时刻来递推。但这样是不对的。

一个点的流动可能断断续续（这种情况是好构造的）。如果冒然存这个点最晚流出的时刻，它给下一个点的贡献就会不对。

如果我们考虑正确性。每一个点存有流动的区间。不好维护+炸空间。

---

这里就有一个非常猎奇的做法（实际上是正解），只模拟前 $n$ 秒。

我们可以发现，在第 $n$ 秒过后，所有的点不会从没水变为有水。

事实上，对于点 $i$，令其离最远的源点有 $dis_i$，在第 $dis_i$ 秒过后，$i$ 不会从没水变为有水。

这个可以使用反证法证明：

如果 $i$ 会在第 $dis_i$ 秒过后从没水变为有水，说明其上游仍然保留有水，但未到达该点。

而上游保留的水最迟会在 $dis_i$ 秒前遍历到 $i$。

这就意味着，要希望这个点在第 $dis_i$ 秒过后从没水变为有水，上游的水也必须是断断续续的。

那么这个问题就变为了 $j$ 是否会在 $dis_i-1$ 秒后从没水变为有水，其中 $j$ 是 $i$ 离最远的源点的路径上的父亲。

显然递推到源头，发现是不会的。

那么我们手动模拟前 $n$ 秒后记录下此时的 $a_x$，在按照最晚流出时刻递推即可。

// #define DEBG 1
#include<bits/stdc++.h>
#define P (998244353ll)
using namespace std;
typedef long long ll;
const int maxn=2015;
const ll inf=1e18;

/*IO*/

int n,m;
ll a[maxn];
vector<int> edge[maxn],needge[maxn];
void input(){
	n=read();m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		edge[u].emplace_back(v);
		needge[v].emplace_back(u);
	}
}

ll ans;

bool nxtvis[2][maxn];//类似spfa，记录下一时刻哪些点要访问
bool solve_n(){
	bool flag=0;
	for(int i=1;i<=n;++i){
		if(a[i]!=0) nxtvis[1][i]=1,flag=1;
		else nxtvis[1][i]=0;
	}
	if(!flag){ans=0;return 1;}
    //特判初始全为0
	for(int tim=1;tim<=n;++tim){
		memset(nxtvis[(tim+1)&1],0,sizeof(bool)*(n+5));
		for(int i=1;i<=n;++i){
			if(!nxtvis[tim&1][i]) continue;
			--a[i];
			if(a[i]!=0) nxtvis[(tim+1)&1][i]=1;
			for(auto y: edge[i]){
				++a[y];
				nxtvis[(tim+1)&1][y]=1;
			}
		}
		flag=0;
		for(int i=1;i<=n;++i){
			if(a[i]!=0) flag=1;
		}
		if(!flag){ans=tim;return 1;}
	}
	return 0;
}

int indu[maxn];
queue<int> que;
ll endtime[maxn];
void solve_big(){
	int last;
	for(int i=1;i<=n;++i){
		if(!edge[i].size()) last=i;
		for(auto y: edge[i]) indu[y]++;
	}
	for(int i=1;i<=n;++i){
		if(!indu[i]) que.push(i);
	}
	while(que.size()){
		ll x=que.front();
		que.pop();

		ll sum=0;
		for(auto pre: needge[x]) sum=(sum+endtime[pre])%P;
		endtime[x]=(a[x]+sum)%P;

		for(auto y: edge[x]){
			--indu[y];
			if(indu[y]==0) que.push(y);
		}
	}
	ans=(endtime[last]+n)%P;
}


void reset(){
	for(int i=0;i<=n+5;++i){
		edge[i].clear();
		needge[i].clear();
		indu[i]=endtime[i]=0;
	}
	while(que.size()) que.pop();
}

int main(){
	int T=read();
	while(T--){
		input();
		if(!solve_n()) solve_big();
		printf("%lld\n",ans);
		// printf("%lld\n",(ans==375)?(376):(ans));  //gjoj神秘数据出锅
		reset();
	}	
	return 0;
}

s