p3387
主要是看看关键路径的求法
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
。。。
一看便是缩点了（这不就是模板吗）；
缩点后一张有向无环图是不存在“回头走”的；
也自然只走了一次 分析
缩点模板，蒟蒻用的是tarjan和spfa做的；
题目目的：
缩点：将一张有向有环的图，变为一张有向无环图，便于操作；
求关键路径：一张AOV图上的最长路（可能不止一条）；
分析：
缩点用tarjan，楼上大佬讲得很好了，这里不加累述；
求关键路径：这是一个无根树，要有一个源点和汇点；
或者每个点都当做根跑一遍；
为了简单我这里用了后者
但题目木有，so我们得自己加一个超级源点和超级汇点；
为了简便我这里使用了SPFA（还是挺快的）；
每条边的权值是是每个出发点的点值； 这里我只给出第二种，用源点和汇点的留给大家思考
直接放代码了
#include<bits/stdc++.h>// 万能头
using namespace std;
const int inf = 500100;// 边数
const int INF = 100100;// 点数
int head[inf];// 原图的
bool vis[INF];// 是否在栈or队列
int sd[INF];// 缩点后的点值
int color[INF];// 原点属于一个强联通分量的一个颜色
int v[inf];// 原点值
int cnt = 0,n,m,total=0;
stack<int> q;// tarjan的栈
struct Edge{
int to;
int next;
}edge[inf];// 原边
struct EDGE{
int to;
int next;
}e[inf];// 现边
int cctv=0;
int tarjan_head[inf];
void add_edge(int x,int y)//加现边
{
cctv++;
e[cctv].next=tarjan_head[x];
e[cctv].to=y;
tarjan_head[x]=cctv;
}
void add(int x,int y)// 加原边
{
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
head[x]=cnt;
}
int dfn[INF];// dfs到的时间
int low[INF];// 可以追溯到的最小的dfn
int tim=1;// dfs的时间
void tarjan(int x)
{
dfn[x]=low[x]=tim;
tim++;
vis[x]=true;
q.push(x);
for(int i=head[x];i;i=edge[i].next)
{
int u=edge[i].to;
if(!dfn[u])
{
tarjan(u);
low[x]=min(low[x],low[u]);//tarjan板子
}
else if(vis[u]) low[x]=min(low[x],dfn[u]);//在栈中
}
if(low[x]==dfn[x])
{
//找到了这个分量的代表元素了
total++;
int y;
do{
//出栈
y=q.top();
q.pop();
vis[y]=false;
color[y]=total;
sd[total]+=v[y];
}while(x!=y);
}
}
int dist[inf];
int spfa(int x)
{
int sum=0;
memset(dist,-0x3f,sizeof(dist));
memset(vis,false,sizeof(vis));//为了节约空间，再用一次吧
queue<int> Q;//spfa的板子
Q.push(x);
vis[x]=true;
dist[x]=0;
while(!Q.empty())
{
x=Q.front();
Q.pop();// 出队
vis[x]=false;
sum=max(sum,dist[x]+sd[x]);//要判断现点上的值和，边上加上的值
for(int i=tarjan_head[x];i;i=e[i].next)
{
int y=e[i].to;
if(dist[y]<dist[x]+sd[x])
dist[y]=dist[x]+sd[x];// 更新
if(vis[y]) continue;
Q.push(y);
}
}
//cout<<"sum :"<<sum<<endl;
return sum;
}
int main()
{
cin>>n>>m;// 输入
for(int i=1;i<=n;i++)
cin>>v[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);// 跑tarjan
}
}
for(int i=1;i<=n;i++)
{
for(int j=head[i];j;j=edge[j].next)
{
int xx=edge[j].to;// 原边，若不是一个强联通分量的，再在现图上加边
if(color[i]!=color[xx])
add_edge(color[i],color[xx]);// 加边
}
}
int ans=0;
for(int i=1;i<=total;i++)
{
ans=max(spfa(i),ans);//跑SPFA
}
cout<<ans<<endl;
return 0;
}