好久没法博客了
这次就水个板子题目吧
tarjan缩点之后重新建图
而且边权应该都是正的（要不我怎么能这么轻松水过去）
在新图上记忆化一下就好了
f[i] 表示 开头选i这个点 的 路径最大值
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+7;
int n,m,w[maxn],f[maxn];
int stak[maxn],top,vis[maxn],dfn[maxn],low[maxn],cnt;//一套trajan
int color[maxn],color_tot,color_w[maxn];//一套染色数组
struct edge {
int u,v,nxt;
}old_e[maxn],new_e[maxn];
int old_head[maxn],old_tot;
int new_head[maxn],new_tot;
void add1(int u,int v) {
old_e[++old_tot].u=u;
old_e[old_tot].v=v;
old_e[old_tot].nxt=old_head[u];
old_head[u]=old_tot;
}
void add2(int u,int v) {
new_e[++new_tot].v=v;
new_e[new_tot].nxt=new_head[u];
new_head[u]=new_tot;
}
void tarjan(int u) {
dfn[u]=low[u]=++cnt;
vis[u]=1;
stak[++top]=u;
for(int i=old_head[u];i;i=old_e[i].nxt) {
int v=old_e[i].v;
if(!dfn[v]) {
tarjan(v);
dfn[u]=min(dfn[u],dfn[v]);
} else
if(vis[v])
dfn[u]=min(dfn[u],low[v]);
}
if(dfn[u]==low[u]) {
++color_tot;
while(stak[top]!=u) {
vis[stak[top]]=0;
color_w[color_tot]+=w[stak[top]];
color[stak[top--]]=color_tot;
}
top--;
color[u]=color_tot;
color_w[color_tot]+=w[u];
vis[u]=0;
}
}
//f[i] 表示 开头选i这个点的路径最大值
int dfs(int u)
{
if(f[u]) return f[u];
int tmp=0;
for(int i=new_head[u];i;i=new_e[i].nxt) {
int v=new_e[i].v;
tmp=max(tmp,dfs(v));
}
if(!tmp) return f[u]=color_w[u];
return f[u]=color_w[u]+tmp;
}
int main()
{
//freopen("testdata.in","r",stdin);
//读入
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&w[i]);
for(int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
add1(u,v);
}
//缩点
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i);
//建新图
for(int i=1;i<=old_tot;++i)
if(color[old_e[i].u]!=color[old_e[i].v])
{
add2(color[old_e[i].u],color[old_e[i].v]);
//cout<<color[old_e[i].u]<<" -> "<<color[old_e[i].v]<<"
";
}
//记忆化搜索
int ans=0;
for(int i=1;i<=color_tot;++i)
ans=max(ans,dfs(i));
//输出ans
printf("%d
",ans);
return 0;
}