社区讨论

萌新过不了tarjan简单题求助

P3627[APIO2009] 抢掠计划参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lrbqk8d1
此快照首次捕获于
2024/01/13 15:18
2 年前
此快照最后确认于
2024/01/13 16:59
2 年前
查看原帖
第三个点t飞了,是复杂度假了还是哪里写挂了求教
CPP
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define re register

using namespace std;
const int N=5e5+10;
int n,m,a[N];
int S,P;
bool H[N],h[N];

//
map < pair<int,int>,bool > mp;
vector <int> G[N],g[N];

int dfn[N],low[N],timing;
int s[N],tot,c[N],col,sum[N];
bool v[N];
void tarjan(int x)
{
	dfn[x]=low[x]=++timing;
	v[x]=true ,s[++tot]=x;
	for(auto y : G[x])
	{
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(v[y]) low[x]=min(low[x],dfn[y]);
	}
	if(low[x]^dfn[x]) return ;
	++col;
	while(x^s[tot])
	{
		int y=s[tot--];
		sum[col]+=a[y],v[y]=false ,c[y]=col;
		h[col]|=H[y];
	}
	tot--;
	sum[col]+=a[x],v[x]=false ,c[x]=col;
	h[col]|=H[x];
}

int q[N];
int f[N];
inline void tuopu()
{
	tot=0;
	q[++tot]=c[S];
	f[c[S]]=sum[c[S]];
	while(tot)
	{
		int x=q[tot--];
		for(auto y : g[x])
		{
			f[y]=max(f[y],f[x]+sum[y]);
			q[++tot]=y;
		}
	}
}
inline int read(){char cr=getchar();int x_=0,fui=1;while(cr<48){if(cr=='-')fui=-1;cr=getchar();}while(cr>47)x_=(x_*10)+(cr^48),cr=getchar();return x_*fui;}
inline void mwrite(int aq){if(aq>9)mwrite(aq/10);putchar((aq%10)|48);}
inline void write(int af,char cr){mwrite(af<0?(putchar('-'),af=-af):af);putchar(cr);}

signed main()
{
	n=read(),m=read();
	for(re int i=1;i<=m;++i)
	{
		int U,V;
		U=read(),V=read();
		G[U].push_back(V);
	}
	for(re int i=1;i<=n;++i) a[i]=read();
	cin>>S>>P;
	for(re int i=1;i<=P;++i)
	{
		int U;
		U=read();
		H[U]=true ;
	}
	for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	for(re int i=1;i<=n;++i)
	{
		for(auto x : G[i])
		{
			if(c[x]==c[i]||mp.find({c[i],c[x]})!=mp.end()) continue ;
			mp[{c[i],c[x]}]=true ;
			g[c[i]].push_back(c[x]);
		//	rd[c[x]]++;
		}
	}
	tuopu();
	int ans=0;
	for(re int i=1;i<=col;++i) if(h[i]) ans=max(ans,f[i]);
	write(ans,' ');
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...