诡异的缩点
2026-07-05 17:10:07
发布于：浙江
10阅读
0回复
0点赞
#include <iostream>
#include <vector>
const int MAX_N=1e4+5,MAX_M=1e5+10;
int n,m,head[MAX_N],cnt,low[MAX_N],dfn[MAX_N],idx,Stake[MAX_N],top,vis[MAX_N],scc_cnt,scc_belong[MAX_N],scc_sum[MAX_N],a[MAX_N],ans=0;
int min(int a,int b){
return a>b?b:a;
}int max(int a,int b){
return a<b?b:a;
}
int dp[MAX_N];
// 链式前向星
struct Edge{
int next,to;
Edge(int a=-1,int b=0):next(a),to(b){}
}edge[MAX_M];
void init(){
for(int i=1;i<=n;i++)head[i]=dp[i]=-1;//顺手初始化 dp
}
void add(int u,int v){
edge[cnt]=Edge(head[u],v);
head[u]=cnt++;
}
// ***************************************
void Tarjan(int u){
dfn[u]=low[u]=++idx/*下标*/; // 记录节点u的时间戳dfn和能追溯到的最早祖先low，并递增全局时间戳idx
vis[u]=1; // 标记节点u当前在栈中
Stake[++top]=u;//入栈 // 将节点u压入栈中
for(int i=head[u];i!=-1;i=edge[i].next){ // 遍历节点u的所有出边
int v=edge[i].to; // 获取边的终点v
if(!dfn[v]){ // 如果节点v尚未被访问过
Tarjan(v); // 递归访问节点v
low[u]=min(low[u],low[v]); // 回溯时，用子节点v的low值更新当前节点u的low值
}else if(vis[v])low[u]=min(low[u],dfn[v]); // 如果节点v已在栈中（说明存在回边指向祖先或同一SCC内的节点），用v的dfn值更新u的low值
}if(dfn[u]==low[u]){ // 如果节点u的dfn等于low，说明u是一个强连通分量的根节点
scc_cnt++; // 强连通分量计数器加1
int p;
//更新
do{
p=Stake[top--]; // 弹出栈顶元素p
vis[p]=0; // 标记节点p已离开栈
scc_belong[p]=scc_cnt; // 记录节点p所属的强连通分量编号
scc_sum[scc_cnt]+=a[p]; // 累加该强连通分量内所有节点的权值
}while(p!=u); // 直到弹出的节点为u为止，完成一个SCC的提取
}
}
std::vector<int> to[MAX_N];
int dfs(int u){//记忆化大法师
if(dp[u]!=-1)return dp[u]; // 如果该状态已计算过，直接返回结果（记忆化搜索）
dp[u]=scc_sum[u]; // 初始化当前SCC的最大权值和为其自身权值和
for(auto v:to[u])dp[u]=max(dp[u],scc_sum[u]+dp[v]); // 遍历缩点后的DAG中的出边，尝试通过子节点v更新最大权值路径
return dp[u]; // 返回从节点u出发能得到的最大权值和
}
int main(){
std::cin >> n >> m;
for(int i=1;i<=n;i++)std::cin >> a[i];
init();
for(int i=1;i<=m;i++){
int u,v;
std::cin >> u >> v;
add(u,v);
}for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i); // 对每个未访问的节点执行Tarjan算法，处理非连通图情况
for(int u=1;u<=n;u++){
int bu=scc_belong[u],bv;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
bv=scc_belong[v];
if(bu==bv)continue; // 如果u和v属于同一个强连通分量，则跳过（内部边不需要保留）
to[bu].push_back(bv); // 否则，在缩点后的DAG中添加从bu到bv的有向边
}
}for(int i=1;i<=n;i++)ans=max(ans,dfs(i)); // 遍历所有缩点后的节点，寻找最大权值路径
std::cout << ans;
return 0;
}
一些诡异的注释是我打的，其他是 AI 打的。后期看看要不要讲一下，先放灌水了
这里空空如也
有帮助，赞一个