这道题用Kosaraju+dp不吸氧会T,有没有大佬帮忙优化一下啊
查看原帖
这道题用Kosaraju+dp不吸氧会T,有没有大佬帮忙优化一下啊
181521
珈乐唯毒楼主2020/5/28 16:11
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int dfn[N],tot,n,m,a,b,from,to,val[N],w[N],co[N],sc,ans[N],anss;
vector<int> g[N],p[N],o[N];
bool jj[N],po[N];
bool vis[N];
void dfs1(int u){
	vis[u]=1;
	for(int i=0;i<g[u].size();i++)
		if(!vis[g[u][i]])dfs1(g[u][i]);
	dfn[++tot]=u;
	return;
}
void dfs2(int u){
	vis[u]=0;
	co[u]=sc;
	for(int i=0;i<p[u].size();i++) 
		if(vis[p[u][i]])dfs2(p[u][i]);
	return;
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		from=read();
		to=read();
		if(from==to)continue;
		g[from].push_back(to);
		p[to].push_back(from);
	}	
	for(int i=1;i<=n;i++)val[i]=read();
	a=read();
	b=read();
	for(int i=1;i<=b;i++){
		from=read();
		jj[from]=1;
	}
	dfs1(a);//第一次dfs 
	for(int i=tot;i>=1;i--){
		if(vis[dfn[i]]){
			sc++;
			dfs2(dfn[i]);
		}
	} //第二次 
	for(int i=1;i<=n;i++){
		if(co[i]==0)continue;
		w[co[i]]+=val[i];
		if(jj[i]==1)po[co[i]]=1;
		for(int j=0;j<p[i].size();j++){
			if(co[i]!=co[p[i][j]])o[co[i]].push_back(co[p[i][j]]);
		}
	}//存新的边(反向) 
	for(int i=1;i<=sc;i++){
		for(int j=0;j<o[i].size();j++){
			ans[i]=max(ans[o[i][j]],ans[i]);
		}
		ans[i]+=w[i];
		if(po[i]==1)
			anss=max(anss,ans[i]);
	}//dp 
	cout<<anss;
	return 0;
}
2020/5/28 16:11
加载中...