社区讨论
萌新过不了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 条回复,欢迎继续交流。
正在加载回复...