TLE on test3,1.03s
查看原帖
TLE on test3,1.03s
375403
NASFsky楼主2023/11/10 13:50

只在第三个点 T 飞了,1.03s
做法是缩点后在 DAG 上跑 dp,但不知道为什么非常之慢。

#include<bits/stdc++.h>
#define N 500200
#define il inline
using namespace std;
int n,m,s,p,ans,id;
int a[N],w[N],f[N];
int dfn[N],low[N],scc[N],ind;
bool ins[N],qwq[N];
stack<int>st;
vector<int>g[N],g1[N];
bool con[8000][8000];
il void tarjan(int u)
{
	dfn[u]=low[u]=++ind;ins[u]=1;st.push(u);
	for(int v:g[u])
	{
		if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
		else if(ins[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		id++;
		while(1)
		{
			int v=st.top();st.pop();
			ins[v]=0;scc[v]=id;
			if(u==v)break;
		}
	}
}
il void dfs(int u,int sum)
{
	sum+=w[u];
	if(sum<=f[u])return;
	f[u]=sum;
	if(qwq[u])ans=max(ans,sum);
	for(int v:g1[u])dfs(v,sum);
}
namespace in
{
    char buf[1<<25],*p1=buf,*p2=buf;
    inline int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    template <typename T>inline void read(T& t){
        t=0;int f=0;char ch=getc();while (!isdigit(ch)){if(ch=='-')f = 1;ch=getc();}
        while(isdigit(ch)){t=t*10+ch-48;ch = getc();}if(f)t=-t;
    }
    template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
}
int main()
{
//	freopen("P3627_3.in","r",stdin);
//	freopen("1.out","w",stdout);
	in::read(n,m);
	for(int i=1,u,v;i<=m;++i)
	{
		in::read(u,v);
		g[u].push_back(v);
	}
	for(int i=1;i<=n;++i)in::read(a[i]);
	in::read(s,p);
	tarjan(s);
	for(int i=1;i<=n;++i)w[scc[i]]+=a[i];
	for(int i=1;i<=n;++i)
	{
		for(int j:g[i])
		{
			if(scc[i]==scc[j]||con[scc[i]][scc[j]])continue;
			g1[scc[i]].push_back(scc[j]);
			con[scc[i]][scc[j]]=1;
		}
	}
	for(int i=1,x;i<=p;++i)
	{
		in::read(x);
		qwq[scc[x]]=1;
	}
	dfs(scc[s],0);
	printf("%d\n",ans);
}
2023/11/10 13:50
加载中...