90pts
```
#include<bits/stdc++.h>
using namespace std;
struct graph1
{
/*
图模板，tarjan 求强连通分量部分。
==========函数表==========
link(x,y,v)
结点 x 向结点 y 连接一条权值为 v 的有向边
x,y 结点编号
v 边权
tarjan_DFS(x,f)
以结点 x 为起始结点，进行 DFS，深度为 f
x 结点编号
f 遍历深度
tarjan()
求强连通分量
==========变量表==========
total_point 总结点数
total_edge 总边数
total_scc 强连通分量数
first[i] 链式前向星
to[i] 链式前向星
next[i] 链式前向星
val[i] 第 i 条边的边权
dfn[i] 第 i 个结点的被遍历的顺序
low[i] 第 i 个结点及其能连向的所有结点中，dfn 的最小值
visit[i] 第 i 个结点已被遍历
scc[i] 第 i 个结点所在的强连通分量编号
S tarjan 需要用到的栈
*/
static const int POINT_MAX=1e5+10,EDGE_MAX=2e5+10;
int total_point=0,total_edge=0,first[POINT_MAX]={0},to[EDGE_MAX]={0},next[EDGE_MAX]={0};
int val[EDGE_MAX]={0};
int dfn[POINT_MAX]={0},low[POINT_MAX]={0},scc[POINT_MAX];
int total_scc=0;
bool visit[POINT_MAX]={0};
stack<int>S;
void link(int x,int y,int v=-1)
{
to[++total_edge]=y;
next[total_edge]=first[x];
first[x]=total_edge;
val[total_edge]=v;
total_point=max(total_point,max(x,y));
}
void tarjan_DFS(int x,int f)
{
dfn[x]=f;
low[x]=f;
S.push(x);
visit[x]=1;
for(int i=first[x];i;i=next[i])
{
if(dfn[to[i]]==0)
{
tarjan_DFS(to[i],f+1);
low[x]=min(low[x],low[to[i]]);
}
else if(visit[to[i]])
low[x]=min(low[x],low[to[i]]);
}
if(dfn[x]==low[x])
{
total_scc++;
scc[x]=total_scc;
visit[x]=0;
while(S.top()!=x)
{
scc[S.top()]=total_scc;
visit[S.top()]=0;
S.pop();
}
S.pop();
}
}
void tarjan()
{
for(int i=1;i<=total_point;i++)
if(!dfn[i])
tarjan_DFS(i,1);
}
};
struct graph2
{
/*
图模板，拓扑排序部分。
==========函数表==========
link(x,y,v)
结点 x 向结点 y 连接一条权值为 v 的有向边
x,y 结点编号
v 边权
topology_sort()
拓扑排序框架
==========变量表==========
total_point 总结点数
total_edge 总边数
first[i] 链式前向星
to[i] 链式前向星
next[i] 链式前向星
val[i] 第 i 条边的边权
in_degree[i] 第 i 个结点的入度
Q 拓扑排序需要的队列
*/
static const int POINT_MAX=1e5+10,EDGE_MAX=2e5+10;
queue<int>Q;
int total_point=0,total_edge=0,first[POINT_MAX]={0},to[EDGE_MAX]={0},next[EDGE_MAX]={0};
int val[EDGE_MAX]={0};
int pval[POINT_MAX]={0};
int in_degree[POINT_MAX];
int dp[POINT_MAX];
void link(int x,int y,int v=-1)
{
to[++total_edge]=y;
next[total_edge]=first[x];
first[x]=total_edge;
val[total_edge]=v;
total_point=max(total_point,max(x,y));
}
void topology_sort()
{
while(!Q.empty())
Q.pop();
for(int i=1;i<=total_point;i++)
for(int j=first[i];j;j=next[j])
in_degree[to[j]]++;
for(int i=1;i<=total_point;i++)
if(in_degree[i]==0)
Q.push(i);
while(!Q.empty())
{
int t=Q.front();
dp[t]=max(dp[t],pval[t]);
Q.pop();
for(int i=first[t];i;i=next[i])
{
dp[to[i]]=max(dp[to[i]],dp[t]+pval[to[i]]);
in_degree[to[i]]--;
if(in_degree[to[i]]==0)
Q.push(to[i]);
}
}
}
};
graph1 G1;
graph2 G2;
int a[100010];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G1.link(x,y);
}
G1.tarjan();
for(int i=1;i<=n;i++)
G2.pval[G1.scc[i]]+=a[i];
for(int i=1;i<=n;i++)
for(int j=G1.first[i];j;j=G1.next[j])
if(G1.scc[i]!=G1.scc[G1.to[j]])
G2.link(G1.scc[i],G1.scc[G1.to[j]]);
G2.topology_sort();
int ans=0;
for(int i=1;i<=G1.total_scc;i++)
ans=max(ans,G2.pval[i]);
for(int i=1;i<=G1.total_scc;i++)
ans=max(ans,G2.dp[i]);
printf("%d",ans);
return 0;
}
```
by TianLuen @ 2022-10-26 23:42:23
40pts
```
#include<bits/stdc++.h>
using namespace std;
struct graph1
{
/*
图模板，tarjan 求强连通分量部分。
==========函数表==========
link(x,y,v)
结点 x 向结点 y 连接一条权值为 v 的有向边
x,y 结点编号
v 边权
tarjan_DFS(x,f)
以结点 x 为起始结点，进行 DFS，深度为 f
x 结点编号
f 遍历深度
tarjan()
求强连通分量
==========变量表==========
total_point 总结点数
total_edge 总边数
total_scc 强连通分量数
first[i] 链式前向星
to[i] 链式前向星
next[i] 链式前向星
val[i] 第 i 条边的边权
dfn[i] 第 i 个结点的被遍历的顺序
low[i] 第 i 个结点及其能连向的所有结点中，dfn 的最小值
visit[i] 第 i 个结点已被遍历
scc[i] 第 i 个结点所在的强连通分量编号
S tarjan 需要用到的栈
*/
static const int POINT_MAX=1e5+10,EDGE_MAX=1e5+10;
int total_point=0,total_edge=0,first[POINT_MAX]={0},to[EDGE_MAX]={0},next[EDGE_MAX]={0};
int val[EDGE_MAX]={0};
int dfn[POINT_MAX]={0},low[POINT_MAX]={0},scc[POINT_MAX];
int total_scc=0;
bool visit[POINT_MAX]={0};
stack<int>S;
void link(int x,int y,int v=-1)
{
to[++total_edge]=y;
next[total_edge]=first[x];
first[x]=total_edge;
val[total_edge]=v;
total_point=max(total_point,max(x,y));
}
void tarjan_DFS(int x,int f)
{
dfn[x]=f;
low[x]=f;
S.push(x);
visit[x]=1;
for(int i=first[x];i;i=next[i])
{
if(dfn[to[i]]==0)
{
tarjan_DFS(to[i],f+1);
low[x]=min(low[x],low[to[i]]);
}
else if(visit[to[i]])
low[x]=min(low[x],low[to[i]]);
}
if(dfn[x]==low[x])
{
total_scc++;
scc[x]=total_scc;
visit[x]=0;
while(S.top()!=x)
{
scc[S.top()]=total_scc;
visit[S.top()]=0;
S.pop();
}
S.pop();
}
}
void tarjan()
{
for(int i=1;i<=total_point;i++)
if(!dfn[i])
tarjan_DFS(i,1);
}
};
struct graph2
{
/*
图模板，拓扑排序部分。
==========函数表==========
link(x,y,v)
结点 x 向结点 y 连接一条权值为 v 的有向边
x,y 结点编号
v 边权
topology_sort()
拓扑排序框架
==========变量表==========
total_point 总结点数
total_edge 总边数
first[i] 链式前向星
to[i] 链式前向星
next[i] 链式前向星
val[i] 第 i 条边的边权
in_degree[i] 第 i 个结点的入度
Q 拓扑排序需要的队列
*/
static const int POINT_MAX=1e5+10,EDGE_MAX=1e5+10;
queue<int>Q;
int total_point=0,total_edge=0,first[POINT_MAX]={0},to[EDGE_MAX]={0},next[EDGE_MAX]={0};
int val[EDGE_MAX]={0};
int pval[POINT_MAX]={0};
int in_degree[POINT_MAX];
int dp[POINT_MAX];
void link(int x,int y,int v=-1)
{
to[++total_edge]=y;
next[total_edge]=first[x];
first[x]=total_edge;
val[total_edge]=v;
total_point=max(total_point,max(x,y));
}
void topology_sort()
{
while(!Q.empty())
Q.pop();
for(int i=1;i<=total_point;i++)
for(int j=first[i];j;j=next[j])
in_degree[to[j]]++;
for(int i=1;i<=total_point;i++)
if(in_degree[i]==0)
Q.push(i);
while(!Q.empty())
{
int t=Q.front();
dp[t]=max(dp[t],pval[t]);
Q.pop();
for(int i=first[t];i;i=next[i])
{
dp[to[i]]=max(dp[to[i]],dp[t]+pval[to[i]]);
in_degree[to[i]]--;
if(in_degree[to[i]]==0)
Q.push(to[i]);
}
}
}
};
graph1 G1;
graph2 G2;
int a[100010];
bool _[10010][10010];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G1.link(x,y);
}
G1.tarjan();
for(int i=1;i<=n;i++)
G2.pval[G1.scc[i]]+=a[i];
for(int i=1;i<=n;i++)
for(int j=G1.first[i];j;j=G1.next[j])
if(G1.scc[i]!=G1.scc[G1.to[j]])
_[G1.scc[i]][G1.scc[G1.to[j]]]=1;
for(int i=1;i<=G1.total_scc;i++)
for(int j=i+1;j<=G1.total_scc;j++)
if(_[i][j])
G2.link(j,i);
G2.topology_sort();
int ans=0;
for(int i=1;i<=G1.total_scc;i++)
ans=max(ans,G2.pval[i]);
for(int i=1;i<=G1.total_scc;i++)
ans=max(ans,G2.dp[i]);
printf("%d",ans);
return 0;
}
```
by TianLuen @ 2022-10-26 23:43:02
60pts
```
#include<bits/stdc++.h>
using namespace std;
struct graph1
{
/*
图模板，tarjan 求强连通分量部分。
==========函数表==========
link(x,y,v)
结点 x 向结点 y 连接一条权值为 v 的有向边
x,y 结点编号
v 边权
tarjan_DFS(x,f)
以结点 x 为起始结点，进行 DFS，深度为 f
x 结点编号
f 遍历深度
tarjan()
求强连通分量
==========变量表==========
total_point 总结点数
total_edge 总边数
total_scc 强连通分量数
first[i] 链式前向星
to[i] 链式前向星
next[i] 链式前向星
val[i] 第 i 条边的边权
dfn[i] 第 i 个结点的被遍历的顺序
low[i] 第 i 个结点及其能连向的所有结点中，dfn 的最小值
visit[i] 第 i 个结点已被遍历
scc[i] 第 i 个结点所在的强连通分量编号
S tarjan 需要用到的栈
*/
static const int POINT_MAX=1e5+10,EDGE_MAX=2e5+10;
int total_point=0,total_edge=0,first[POINT_MAX]={0},to[EDGE_MAX]={0},next[EDGE_MAX]={0};
int val[EDGE_MAX]={0};
int dfn[POINT_MAX]={0},low[POINT_MAX]={0},scc[POINT_MAX];
int total_scc=0;
bool visit[POINT_MAX]={0};
stack<int>S;
void link(int x,int y,int v=-1)
{
to[++total_edge]=y;
next[total_edge]=first[x];
first[x]=total_edge;
val[total_edge]=v;
total_point=max(total_point,max(x,y));
}
int tim=0;
void tarjan_DFS(int x)
{
dfn[x]=++tim;
low[x]=tim;
S.push(x);
visit[x]=1;
for(int i=first[x];i;i=next[i])
{
if(dfn[to[i]]==0)
{
tarjan_DFS(to[i]);
low[x]=min(low[x],low[to[i]]);
}
else if(visit[to[i]])
low[x]=min(low[x],low[to[i]]);
}
if(dfn[x]==low[x])
{
total_scc++;
scc[x]=total_scc;
visit[x]=0;
while(S.top()!=x)
{
scc[S.top()]=total_scc;
visit[S.top()]=0;
S.pop();
}
S.pop();
}
}
void tarjan()
{
for(int i=1;i<=total_point;i++)
if(!dfn[i])
tarjan_DFS(i);
}
};
struct graph2
{
/*
图模板，拓扑排序部分。
==========函数表==========
link(x,y,v)
结点 x 向结点 y 连接一条权值为 v 的有向边
x,y 结点编号
v 边权
topology_sort()
拓扑排序框架
==========变量表==========
total_point 总结点数
total_edge 总边数
first[i] 链式前向星
to[i] 链式前向星
next[i] 链式前向星
val[i] 第 i 条边的边权
in_degree[i] 第 i 个结点的入度
Q 拓扑排序需要的队列
*/
static const int POINT_MAX=1e5+10,EDGE_MAX=2e5+10;
queue<int>Q;
int total_point=0,total_edge=0,first[POINT_MAX]={0},to[EDGE_MAX]={0},next[EDGE_MAX]={0};
int val[EDGE_MAX]={0};
int pval[POINT_MAX]={0};
int in_degree[POINT_MAX];
int dp[POINT_MAX];
void link(int x,int y,int v=-1)
{
to[++total_edge]=y;
next[total_edge]=first[x];
first[x]=total_edge;
val[total_edge]=v;
total_point=max(total_point,max(x,y));
}
void topology_sort()
{
while(!Q.empty())
Q.pop();
for(int i=1;i<=total_point;i++)
for(int j=first[i];j;j=next[j])
in_degree[to[j]]++;
for(int i=1;i<=total_point;i++)
if(in_degree[i]==0)
Q.push(i);
for(int i=1;i<=total_point;i++)
dp[i]=pval[i];
while(!Q.empty())
{
int t=Q.front();
Q.pop();
for(int i=first[t];i;i=next[i])
{
dp[to[i]]=max(dp[to[i]],dp[t]+pval[to[i]]);
in_degree[to[i]]--;
if(in_degree[to[i]]==0)
Q.push(to[i]);
}
}
}
};
graph1 G1;
graph2 G2;
int a[100010];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G1.link(x,y);
}
G1.tarjan();
for(int i=1;i<=n;i++)
for(int j=G1.first[i];j;j=G1.next[j])
if(G1.scc[i]!=G1.scc[G1.to[j]])
G2.link(G1.scc[i],G1.scc[G1.to[j]]);
for(int i=1;i<=n;i++)
G2.pval[G1.scc[i]]+=a[i];
G2.topology_sort();
int ans=0;
for(int i=0;i<=G2.total_point;i++)
ans=max(ans,G2.pval[i]);
for(int i=0;i<=G2.total_point;i++)
ans=max(ans,G2.dp[i]);
printf("%d",ans);
return 0;
}
```
by TianLuen @ 2022-10-26 23:43:31
@[TianLuen](/user/239988) `dfs` 序不是深度，每个节点的 `dfs` 序需要不同。
by Usada_Pekora @ 2022-10-27 07:18:05
只需把 tarjan 改成 `dfn[x] = low[x] = ++idx;`。
by Usada_Pekora @ 2022-10-27 07:18:42
@[TianLuen](/user/239988) 你想知道的应该是你的那份代码是怎么过的。
by XHY20180718 @ 2022-11-06 16:40:21
@[TianLuen](/user/239988) dfn是时间戳，指的是遍历到该店的时间点，而不是深度额。。。
你的AC代码应该是凑巧过的（个人猜测）。
by XHY20180718 @ 2022-11-06 16:41:58