当前位置: 首页 > news >正文

P3387 【模板】缩点 tarjan

解题思路

问题分析:

  • 给定有向图,每个点有权值,求路径最大点权和

  • 允许重复经过边和点,但重复点的权值只计算一次

  • 关键:强连通分量内的点可以任意走,权值只需累加一次

Tarjan缩点算法:

  1. 求强连通分量(SCC):使用Tarjan算法找出所有SCC

  2. 缩点建新图:将每个SCC缩成一个节点,形成DAG

  3. 拓扑排序+DP:在DAG上求最长路径

代码注释

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10,inf = 0x3f3f3f3f;// g: 原图的邻接表, e: 缩点后新图的邻接表
vector<int> g[N],e[N];// Tarjan算法相关
int dfn[N],low[N],id;    // dfn:深度优先序, low:能回溯到的最小dfn, id:时间戳计数器
int q[N],top,inq[N];     // q:模拟栈, top:栈顶, inq:标记节点是否在栈中
int n,m;// 缩点相关
int scc[N],sccnt;        // scc[i]:节点i所属的SCC编号, sccnt:SCC计数器
int sccval[N];           // sccval[i]:第i个SCC的总权值// 拓扑排序相关
ll a[N],f[N];            // a[i]:原节点权值, f[i]:以SCC i结尾的最大路径和
int rd[N];               // rd[i]:SCC i的入度// Tarjan算法求强连通分量
void tarjan(int x)
{dfn[x] = low[x] = ++id;    // 初始化当前节点的dfn和lowq[++top] = x;              // 节点入栈inq[x] = 1;                // 标记节点在栈中// 遍历所有邻接节点for(int i = 0; i < g[x].size(); i++){int y = g[x][i];if(dfn[y] == 0){        // 树边:y未被访问
            tarjan(y);low[x] = min(low[x],low[y]);  // 回溯时更新low值
        }else if(inq[y]) low[x] = min(low[x],dfn[y]);  // 回边:y在栈中
    }// 找到SCC的根节点if(low[x] == dfn[x]){sccnt++;while(1){int y = q[top--];     // 弹出栈顶节点inq[y] = 0;           // 标记不在栈中scc[y] = sccnt;       // 记录节点所属SCCsccval[sccnt] += a[y]; // 累加SCC权值if(x == y) break;     // 弹出直到遇到根节点x
        }}
}// 拓扑排序求DAG最长路径,注意拓扑排序中用的是新图e,而非g 
void topsort()
{queue<int> q;ll ans = 0;// 初始化:所有入度为0的SCC入队for(int i = 1; i <= sccnt; i++){    f[i] = sccval[i];         // 初始值为SCC自身权值if(rd[i] == 0) q.push(i); // 入度为0的入队
    }// 拓扑排序while(q.size()){int x = q.front(); q.pop();// 遍历x的所有出边for(int i = 0; i < e[x].size(); i++){int y = e[x][i];rd[y]--;  // 入度减1// 状态转移:f[y] = max(f[y], f[x] + sccval[y])f[y] = max(f[y],f[x] + sccval[y]);ans = max(ans,f[y]);  // 更新答案if(rd[y] == 0) q.push(y);  // 入度为0时入队
        }}// 确保找到最大值(处理没有入度的孤立SCC)for(int i = 1; i <= sccnt; i++) ans = max(ans,f[i]);cout << ans;
}int main()
{// 输入处理cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];  // 读入点权for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;g[x].push_back(y);  // 构建原图
    }// 步骤1: Tarjan算法求所有强连通分量for(int i = 1; i <= n; i++){if(dfn[i] == 0) tarjan(i);  // 对每个未访问节点执行Tarjan
    }// 步骤2: 构建缩点后的新图(DAG)for(int i = 1; i <= n; i++){for(int j = 0; j < g[i].size(); j++){int y = g[i][j];if(scc[i] != scc[y]){  // 不同SCC之间的边e[scc[i]].push_back(scc[y]);  // 添加新图的边rd[scc[y]]++;                 // 目标SCC入度加1
            }}}// 步骤3: 拓扑排序求最长路径
    topsort();return 0;
}

 

http://www.hskmm.com/?act=detail&tid=27595

相关文章:

  • 构建高效AI代理的完整指南:从基础组件到生产级工作流
  • 灵感本位审计框架:为创造性AI建立直达真相的信任机制——Ai元人文
  • 2025学校家具定制厂家最新推荐榜:书包柜,图书架,宿舍配套上下床,书桌等类型全覆盖,专业设计与安全品质深度解析
  • 【每日一面】盒子模型
  • 日总结 9
  • 为什么没有做出题目喵?
  • 杂题选做
  • kettle插件-国产数据库瀚高插件,助力国产数据库腾飞
  • 利用旋钮控制小灯亮度
  • 37 ACwing 298 Fence 题解
  • 35 ACwing 297 The Battle Chibi 题解
  • 一款由网易出品的免费、低延迟、专业的远程控制软件,支持手机、平板、Mac 、PC、TV 与掌机等多设备远控电脑!
  • 计划管理
  • 苍穹外卖第二天(Nginx如何配置、MD5加密)
  • aardio跨窗口传递变量
  • AI在简单视觉推理谜题中的挑战
  • 自动引入的element-plus覆盖tailwindcss样式冲突解决方法
  • 已严肃完成今日96种状态的超级神仙DP大学习
  • P3388 【模板】割点(割顶) tarjan
  • new day
  • 10.9每日总结
  • vLLM 吞吐量优化实战:10个KV-Cache调优方法让tokens/sec翻倍
  • Linux之周期性定时任务实践
  • MyBatis-Plus 的 QueryWrapper 应用以及在内存中处理JSON数组字符串匹配
  • P9461 「EZEC-14」众数 II
  • 提升
  • 详细介绍:win11 安装 WSL2 Ubuntu 并支持远程 SSH 登录
  • Ai元人文:论智能的“全息定帧”与“渐进式显影”机制
  • 24 LCA模拟赛2T4 colorful 题解
  • 23 LCA模拟赛2T2 异或排列 题解