4.14~4.19学习总结

· · 个人记录

【叮咚，您的本周学习总结已生成，请注意查收】

1、 学了什么

图论：强连通分量，双连通分量
主刷题目：缩点、点双连通分量、边双连通分量。

2、做题情况

缩点

初次思路：遍历整个图，求最大点权和（成功RE）
二次思路：看了一下oi-wiki,考虑求强连通分量，但是没有统计点权之和(全部WA)
三次思路：看了几篇题解，又在oi-wiki上过了一下缩点（SCC：Tarjan）、有向无环图和拓扑排序（DAG），稍微想了一下题目和DAG（有向无环图）的关系，但是因为习惯性地在链式前向星中打了无向图的储存方式，还是没过（AC×7，WA×4）
最终思路:重新把题目过了一遍，看见了题目第一行的“给定一个 n 个点 m 条边有向图”，把链式前向星的无向储存改为有向储存（终于AC）

点双连通分量

年初在oj里看到的题，然后自己参考着做了（无抄袭）。
思路大概是这样：链式前向星储存无向图，根据点双连通分量的性质利用了割点（因为是点）和DFS搜索树中的dfn，所以在用链式前向星后以类似于搜索树（Tarjan）的算法求得DCC。
因为无法确定单个点的双连通分量个数，也为了防止不必要的空间占用（防止MLE），用了动态数组vector。 经过几次调试后AC了。

边双连通分量

还是年初时在oj看到的题，还是过了一遍知识后参考着做了（还是无抄袭）。
思路：依旧用了链式前向星存无向图，根据边双连通分量的性质利用了桥（因为是边）和DFS，为防止MLE开了vector，也是调过了已知样例，AC。

经验教训

  1. 看好题，不要因习惯性动作而丢分。
  2. 如果样例都没过先别急着提交，先找一下知识点。
    以上经验来自P3387

    3、小测情况

    总分：175’ / 实际：25’

    A [COCI 2024/2025 #1] 飞跃 / Skokovi

    虽然这次少有的没有爆0，但坏消息是那是道橙题。
    得分点在subtask2，其他两个subtask不是TLE就是AC,这表明思路没错，错就错在dfs超时。
    原思路：类似于“能不能跳过去”和“跳过去后又能跳到哪里”，考虑了一下dfs或dp，但是由于dp太久没用而且推不出动态转移方程，用了dfs。
    为了保证subtask2的数据能稳过，开了个O(n^2)的循环，后来检查代码时发现其实和dfs差不多。
    现思路：后来看了下算法标签——“二分”，还是没想出来，去调试第二题去了。

    B [蓝桥杯 2023 国 A] 相连的边

    少有的所有subtask均没有超时，但是全员WA。
    原思路：习惯性地用了链式前向星储存数据，并考虑以遍历整个“图”的方式来找到“边权”（即长度）最长的三条边中的四个点。
    但是由于遍历时处理不当+调试时间不足，样例都过不了，更不用说代码能过某个subtask的一个测试点了……
    现思路：重新看题目时，看到了给定一棵包含 n 个结点的树，思考了一下源代码中的链式前向星，又转向了查询最大连通边之和的部分。看了几遍题解——“树上遍历”和“要么是菊花图，要么是链”，因为对树形数据结构已经不熟悉，尝试了后者。
    可是两次代码不知怎么回事突然“变异”。
    一次莫名RE（运行着运行着突然崩溃了）。
    一次不知怎么回事突然CE（在编译器上编译的时候突然蹦到了“后台运行程序”，蹦出了类似于“这个cmp函数不能当作函数使用”的error，上网搜索了以后发现和网上原因完全不一致）。
    总之都没调出来

    4、学习感受

    做作业时基本都能运用，但一到小测就突然“掉线”。思路问题已经减少，更多的是题目解析能力和代码构造能力偏弱，再加上接触“图论”的时间不长及太久没碰C++，一“盲眼”就“踩雷”。
    感受很简单：我果然还是太菜了