您为什么不写拓扑啊/kk
by _Hugoi_ @ 2023-08-10 08:06:31
把后边改成记搜过了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=2e5+10;
int h[N],e[M],ne[M],w[N],idx;
int dfn[N],low[N],id[N],timestamp,scc_cnt;
int stk[N],top;
int is_stk[N],x[N],y[N];
int sz[N];
int f[N];
int n,m;
void add(int a,int b){
e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
void tarjan(int u)
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u,is_stk[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(is_stk[j])
{
low[u]=min(low[u],dfn[j]);
}
}
if(dfn[u]==low[u])
{
int y;
scc_cnt++;
do
{
y=stk[top--];
is_stk[y]=false;
id[y]=scc_cnt;
sz[scc_cnt]+=w[y];
}while(y!=u);
}
}
void search(int x){
if(f[x]) return ;
f[x]=sz[x];
int maxsum = 0;
for(int i=h[x];~i;i=ne[i]){
if(!f[e[i]]) search(e[i]);
maxsum=max(maxsum,f[e[i]]);
}
f[x]+=maxsum;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
add(x[i],y[i]);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=idx;i++) e[i]=ne[i]=0;
memset(h,-1,sizeof h);
idx=0;
for(int i=1;i<=m;i++)
{
if(id[x[i]]!=id[y[i]]){
add(id[x[i]],id[y[i]]);
}
}
int ans=0;
for(int i=1;i<=scc_cnt;i++){
if(!f[i]){
search(i);
ans=max(ans,f[i]);
}
}
printf("%d",ans);
return 0;
}
```
by _Hugoi_ @ 2023-08-10 08:49:15
@[Richard_Whr](/user/525375)
by _Hugoi_ @ 2023-08-10 08:50:08
@[_Hugoi_](/user/525402) 因为tarjan过后scc_cnt的倒序就是拓扑序啊，他是深搜出来的，深搜序列的倒序就是拓扑序啊hhh
by Richard_Whr @ 2023-08-10 09:14:57
@[Richard_Whr](/user/525375) 我的意思是我写的拓扑 所以看不太懂你写的（这个题其实不用拓扑也行
by _Hugoi_ @ 2023-08-10 10:53:57
所以你过了吗
by _Hugoi_ @ 2023-08-10 10:54:29
@[_Hugoi_](/user/525402) 我觉得如果记忆化搜索的话是用儿子更新父亲，那就相当于这是个拓扑图但是边都是反着的，但我觉得我的建边没毛病啊【捂脸】（请ycy大佬指出我哪里错了好不好）
深搜倒序就是拓扑序可以这样理解：
当前强连通分量出栈的时候，因为儿子都被搜过了，再也没有强连通分量会贡献出他的出度了，也就是说他不能再有儿子了，只能当别人的儿子了，最后出栈的就是祖宗嘛
by Richard_Whr @ 2023-08-10 10:58:27
不是，你这倒数第二个循环里的else根本不会被使用a
by _Hugoi_ @ 2023-08-10 12:00:39
深搜倒序就是拓扑序是不是只在只有一个入度为0的点时才行a？不太懂
by _Hugoi_ @ 2023-08-10 12:04:49
@[Richard_Whr](/user/525375) 改动的地方我标记出来了
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e4+10,M=2e5+10;
int h[N],e[M],ne[M],w[N],idx;
int hs[N];
int dfn[N],low[N],id[N],timestamp,scc_cnt;
int stk[N],top;
int is_stk[N];
int sz[N];
int f[N];
int n,m;
void add(int h[],int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++timestamp;
stk[++top]=u,is_stk[u]=true;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(is_stk[j])
{
low[u]=min(low[u],dfn[j]);
}
}
if(dfn[u]==low[u])
{
int y;
scc_cnt++;
do
{
y=stk[top--];
is_stk[y]=false;
id[y]=scc_cnt;
sz[scc_cnt]+=w[y];
}while(y!=u);
}
}
int main()
{
memset(h,-1,sizeof h);
memset(hs,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
add(h,a,b);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
set<PII> S;
for(int i=1;i<=n;i++)
{
for(int j=h[i];~j;j=ne[j])//改为j=h[i]
{
int k=e[j];
int a=id[i],b=id[k];
if(a!=b&&!S.count({a,b}))
{
add(hs,a,b);
S.insert({a,b});
}
}
}
int res=0;
for(int i=scc_cnt;i>=1;i--)
{
if(!f[i])
{
f[i]=sz[i];
}
// 删去else
for(int j=hs[i];~j;j=ne[j])
{
int k=e[j];
f[k]=max(f[k],f[i]+sz[k]);
}
}
for(int i=scc_cnt;i>=1;i--)
{
res=max(res,f[i]);
}
printf("%d",res);
return 0;
}
```
by 1001a @ 2023-08-11 11:33:33