缩点
什么是强连通分量
我们把一个图中如果任一点都可以到达其他点则称这个图时一个联通分量，当这个联通分量最大时，便是强连通分量。
如何处理这道题？
遇到这种有环的题目显然判断重复走路时很麻烦的，我们很明显可以发现当几个点可以相互到达时我们可以把它当成一个点来处理，因为从这个图的任一点出发可以达到任意其他的点，且权值可以累加，那我们怎么来判断强连通分量。
解锁tarjan奥义。。
首先我们维护两个数组dfn,low，dfn[i]是i点的进入时间，low[i]是从i点出发，所能访问到的最早的进入时间，这就可以表示出在深搜时是否有环的情况。
那么怎么来求low数组呢？ 对于一条边(u,v),如果v没有被访问过那么继续访问v节点，此时low[u]=min(low[v],low[u]);这是因为可能下一个访问的节点会回溯到他们的祖先；
然后如果vis[v]==1已被访问过，那么就可以使low[u]=min(low[u],dfn[v]);更新low可以回溯的最小值；
然后记住用一个栈来存贮每一个强连通分量中的点
最后 放上代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int to,from;
int next;
}a1[100001],a2[100001];
int maxn,cnt,cnt1,n,m,head[10001],h[10001],p[10001];
int stac[10001],top,id,aa[10001],f[10001];
int dfn[10001],low[10001],vis[10001],sd[10001];//码风有点丑
void add(int a,int b)
{
a1[++cnt].to=b;
a1[cnt].from=a;
a1[cnt].next=head[a];
head[a]=cnt;
}
void tarjan(int u)
{
dfn[u]=low[u]=++id;//初始标记
vis[u]=1;
stac[++top]=u;//压入栈中缩点
for(int i=head[u];i;i=a1[i].next)
{
if(!dfn[a1[i].to])
{
tarjan(a1[i].to);//如果没被访问过
low[u]=min(low[u],low[a1[i].to]);
}
else if(vis[a1[i].to])//如果已被访问过
low[u]=min(low[u],dfn[a1[i].to]);
}
if(dfn[u]==low[u])//当已经找到强连通分量时
{
int y;
while(1)
{
y=stac[top--];//将栈中值取出缩成一个点
sd[y]=u;
vis[y]=0;//标记为0
if(u==y) break;
p[u]+=p[y];//转移权值
}
}
}
int dfs(int k)
{
if(f[k]) return f[k];
int ans=0;
for(int i=h[k];i;i=a2[i].next)
{
ans=max(ans,dfs(a2[i].to));
}
return f[k]=ans+p[k];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>p[i];
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i); //因为可能存在一个点单独为强连通分量，所以需要扫一遍
for(int i=1;i<=m;i++)
{
int x=sd[a1[i].from],y=sd[a1[i].to];
if(x!=y)//存入新的邻接表中
{
a2[++cnt1].to=y;
a2[cnt1].from=x;
a2[cnt1].next=h[x];
h[x]=cnt1;
}
}
for(int i=1;i<=n;i++)
{
if(!f[sd[i]])
maxn=max(maxn,dfs(sd[i]));//记忆化搜索没什么好讲的吧。。
}
cout<<maxn;
return 1;//防伪标记
}后记： 如果想学习割点的知识可以看我的另一篇博客：blog
看不懂的话实属正常情况，因为我菜啊QAQ。