70pts wa拓扑排序部分求助
查看原帖
70pts wa拓扑排序部分求助
121813
老子是北瓜楼主2021/8/24 20:24

百分之百肯定是主函数中拓扑排序的部分写错了,但是不知道还有什么情况没有考虑到,求大佬帮忙看看,万分感谢!

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#define N 1000005
#define mod 998244353
using namespace std;

int n,m,in[N],type[N],p[N],sz,T;
long long mul[N],a[N],val[N],q[N],times[N];
bool vis[N];
vector<int> g[N];

void dfs1(int u)
{
    if(type[u]==2)
    {
    	mul[u]=mul[u]*val[u]%mod;
		return ;
    }
    if(type[u]==3)
    {
        for(int i=0; i<g[u].size(); ++i)
        {
            int v=g[u][i];
            if(vis[v]==0){
            	vis[v]=1;
        		dfs1(v);
        	}
            mul[u]=mul[u]*mul[v]%mod;
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%lld",&a[i]);
    scanf("%d",&m);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d",&type[i]);
        if(type[i]==1) scanf("%d%lld",&p[i],&val[i]);
        if(type[i]==2) scanf("%lld",&val[i]);
        if(type[i]==3)
        {
            scanf("%d",&sz);
            int tmp;
            for(int j=1; j<=sz; ++j)
            {
                scanf("%d",&tmp);
                g[i].push_back(tmp);
                ++in[tmp];
            }
        }
    }
    scanf("%d",&T);
    ++m;
    type[m]=3;
    for(int i=1; i<=T; ++i)
    {
        int tmp;
        scanf("%d",&tmp);
        g[m].push_back(tmp);
        ++in[tmp];
    }
	
    for(int i=1; i<=m; ++i)
		mul[i]=1;
    vis[m]=1;
    
    dfs1(m);
    
    for(int i=1; i<=n; ++i)
    	a[i]=a[i]*mul[m]%mod;

	int l=0,r=0;
	for(int i=m; i>=1; --i)
		if(in[i]==0) 
			q[++r]=i;
	times[m]=1;
	
	while(l<r)
	{
		++l;
		int u=q[l];
		long long w=times[u];
		for(int i=g[u].size()-1; i>=0; --i)
		{
			int v=g[u][i];
			--in[v];
			times[v] += w;
			if(type[v]==1) a[p[v]]=(a[p[v]] + val[v]*w%mod)%mod;
			if(type[v]==3 && in[v]==0) q[++r]=v;
			w=w*mul[v]%mod;
		}
	}
	
	for(int i=1; i<=n; ++i)
		cout<<a[i]<<" ";
    return 0;
}
2021/8/24 20:24
加载中...