[心之碎片] - 图的连通性
专题包括{:10_249:}{:10_266:}{:10_254:}点双, 边双, 强连通分量, 圆方树
需要注意的是这些割点割边强连通分量的判定方式不要搞混
SCC 序很重要, 有时候不需要建新图, 可以直接通过 SCC 编号来看, SCC 小的是在底下找到的, 大的是在上面找到的
遇到连通性相关要考虑这些算法进行简化, 别忘了线段树优化建图等等辅助
思想就是把图变成树, 做树上问题
有向图的 SCC (强连通分量)
模板
void Tarjan(int u) {
low = dfn = ++tot;
stk[++top] = u;
instk = 1;
for (auto v : e) {
if (!dfn) {
Tarjan(v);
low = min(low, low);
} else if (instk)
low = min(low, dfn);
}
if (low == dfn) {
int v;
scc++;
while (1) {
v = stk;
instk = 0;
id = scc;
if (v == u)
break;
}
}
}
一般就是用来缩点然后把图变成 DAG 的, 可以跑 dp 或者别的
G - 拿钱走人
给个点条边的有向图，每个点有一些钱，当你经过这个点时可以拿走这些钱。
现在有一个起点和多个终点，你需要从起点出发，在某个终点结束，并且带走尽量多的钱，问你最多能带走多少钱？
缩点然后拓扑排序跑 dp
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
vector<int> e, g;
int n, m, p, s;
int dfn, low, tot;
int stk, top;
bitset<N> instk, ised;
int val, cnt, id;
int arr, f;
void Tarjan(int u) {
dfn = low = ++tot;
stk[++top] = u;
instk = 1;
for (auto v : e) {
if (!dfn) {
Tarjan(v);
low = min(low, low);
} else if (instk)
low = min(low, dfn);
}
if (low == dfn) {
int v;
cnt++;
while (1) {
v = stk;
instk = 0;
id = cnt;
val += arr;
if (u == v)
break;
}
}
}
// g 图上的 DP
int dfs(int u) {
if (f > 0)
return f;
f = -1e9;
if (ised)
f = 0;
for (auto v : g) {
f = max(f, dfs(v));
}
f += val;
return f;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
e.emplace_back(b);
}
for (int i = 1; i <= n; i++) {
cin >> arr;
}
// 必须注意不能和上面的循环一起写, 调代码的时候注意看当前有没有没求过的数值
for (int i = 1; i <= n; i++) {
if (!dfn)
Tarjan(i);
}
cin >> s >> p;
s = id;
for (int i = 1; i <= p; i++) {
int x;
cin >> x;
ised] = 1;
}
// 建图
for (int i = 1; i <= n; i++) {
for (auto j : e) {
if (id != id) {
g].emplace_back(id);
}
}
}
cout << dfs(s);
return 0;
}
P3119 Grass Cownoisseur G
这里本来应该拓扑排序的, 但是我们只关心能不能到, 所以按照 scc 编号的大小关心来看就好, 最后判断能否拼起来
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> e, g;
int n, m;
int dfn, low, tot;
int bel, scc, siz;
int stk, top;
bitset<N> instk;
void Tarjan(int u) {
dfn = low = ++tot;
stk[++top] = u;
instk = 1;
for (auto v : e) {
if (!dfn) {
Tarjan(v);
low = min(low, low);
} else if (instk)
low = min(low, dfn);
}
if (dfn == low) {
int v;
scc++;
do {
v = stk;
instk = 0;
bel = scc;
siz++;
} while (u != v);
}
}
// 正向, 反向
int a, b, ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
e.emplace_back(b);
}
for (int i = 1; i <= n; i++) {
if (!dfn)
Tarjan(i);
}
if(scc == 1){
cout << siz;
return 0;
}
for (int i = 1; i <= n; i++) {
for (auto j : e) {
if (bel != bel) {
g].emplace_back(bel);
}
}
}
memset(a, -0x3f, sizeof(a));
memset(b, -0x3f, sizeof(b));
a] = siz];
b] = 0;
// bel 能到达地方的最大值
for (int i = bel; i; i--) {
for (auto j : g) {
a = max(a, a + siz);
}
}
// 能到达 bel 的最大值
for (int i = bel + 1; i <= scc; i++) {
for (auto j : g) {
b = max(b, b + siz);
}
}
for (int i = 1; i <= scc; i++) {
for (auto j : g) {
// 想改变方向的是 i-j 这条边, i 自然是在 bel 上面, j 在 bel 下面
// 如果不是这样就不用改了, 自己成环了
if (i >= bel && j <= bel) {
ans = max(ans, a + b);
}
}
}
cout << ans;
return 0;
}
有向图的 vDCC(点双连通分量)eDCC(边双连通分量) 圆方树
BZOJ 3331
建圆方树, 树上差分
vector<int> e, rst;
// 圆方树: 找出所有 vDCC, 每个点断边, 每个点向含有这个点的 vDCC 连边
int dfn, low, tot;
int stk, top, dcc;
void Tarjan(int u) {
dfn = low = ++tot;
stk[++top] = u;
for (auto v : e) {
if (!dfn) {
Tarjan(v);
low = min(low, low);
if (low >= dfn) {
int cur = 0;
dcc++;
while (1) {
cur = stk;
rst.emplace_back(dcc);
rst.emplace_back(cur);
if (cur == v)
break;
}
rst.emplace_back(dcc);
rst.emplace_back(u);
}
} else
low = min(low, dfn);
}
}
一九八四
给一个图, 有操作
1 a b x y 问删掉 (x, y) 这个边, a 和 b 能不能连通
2 a b x 问删掉 x 这个点, a 和 b 能不能连通
先求一下 low 和 dfn, 考虑在搜索树上分类讨论(这玩意一定要分清楚)
// x 是否是 y 的子节点
bool Issub(int x, int y) { return (dfn >= dfn && dfn <= r); }
void Up(int& x, int dist) {
for (int i = 17; i >= 0; i--) {
if ((dist >> i) & 1) {
x = f;
}
}
}
bool Checkdege(int a, int b, int x, int y) {
// 让 x 是 y 的子节点
if (dfn < dfn)
swap(x, y);
// 不是树边
if (f != y)
return 1;
// 都在或者都不在子树
if (Issub(a, x) == Issub(b, x))
return 1;
// 如果有一个点在子树, 判断 (x, y) 是否是割边
return (low < dfn);
}
bool Checkcutv(int a, int b, int x) {
// 都不在子树
if (!Issub(a, x) && !Issub(b, x))
return 1;
// 都在子树, 看看 lca 是否是 x
if (Issub(a, x) && Issub(b, x)) {
Up(a, dep - dep - 1);
Up(b, dep - dep - 1);
return (a == b || (low < dfn && low < dfn));
}
// 其中一个在子树, 判断割点
if (Issub(b, x) && !Issub(a, x))
swap(a, b);
Up(a, dep - dep - 1);
return (low < dfn);
} 好的，让我们来聊聊图的连通性和强连通分量（SCC）的问题，保证你在这个过程中不会迷失在图的海洋中！
### 图的连通性
想象一下，你在一个朋友的聚会上，一个个的朋友就像图中的点（vertex），而朋友之间的关系就像图中的边（edge）。如果所有的朋友都能通过某种关系（直接或间接的）互相联系，那么这个聚会就是“连通”的。反之，如果有一些朋友是孤独的，那就意味着这个聚会并不是完全连通的。
### 强连通分量
对于有向图，我们多了一个概念，那就是“强连通分量”。这就像你有一群朋友，每个人都至少可以通过关系互相到达其他人。比如，如果你可以从A到B再到C，且从C可以回到A，那“A、B、C”可以算作一个强连通分量。这听起来是不是有点复杂？别担心，接下来我们简单讲解如何找到这些强连通分量的方法。
### Tarjan算法
我们可以用**Tarjan算法**来找到强连通分量。想象一下这是你的图灵（图与灵魂的结合）。这个算法的基本思路是深度优先搜索（DFS），如下：
1. **初始化状态**：给每个节点赋初始值。
2. **递归搜索**：当你访问一个子节点时，更新当前节点的`low`值。
3. **形成组件**：如果当前节点的`low`等于其`dfn`值，那么我们找到了一个强连通分量。
使用Tarjan算法就像是在朋友聚会中玩“抓人游戏”，每次抓到的人都要把周围的朋友拉入自己的小队，直到所有能够互相联系的人都被抓进来了。
### 有向图中的最大收益问题
假如你朋友聚会中的每个人都携带了一些现金，你希望从一个起点开始，到达多个终点，同时尽可能多地“收集”这些现金。这里就可以通过之前提到的SCC来“缩点”，然后使用拓扑排序和动态规划来找到最大收益，就像是在聚会上找到最佳的“收钱”路线！
下面是一个简单的框架：
1. **缩点**：将每个强连通分量看作一个点，形成新的DAG（有向无环图）。
2. **DP求解**：从起点开始，利用动态规划来计算每个点可以得到的最大现金。
### 代码示例
虽然最后的代码有点长，但其实它就是上面提到的思想的具体实现。你只需保持思路清晰，确保在任何情况下都不会“迷路”。记得，计算图的时候一定要小心割点和割边，确保你的“朋友聚会”永远是连通的！
### 总结
通过将图转化为树的形式，我们可以更好、更高效地处理各种问题。不管是找朋友还是收钱，紧握住连通性和强连通分量的钥匙，无论何时，你都能在图的世界中游刃有余！
希望你能在图的旅途中一路顺风，收获满满！而且别忘了最重要的一点——即使是图形和数据结构，偶尔也要给自己留点幽默感哦！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-8-11 21:22
好的，让我们来聊聊图的连通性和强连通分量（SCC）的问题，保证你在这个过程中不会迷失在图的海洋中！
# ...
教我一下同余最短路的原理 柿子饼同学 发表于 2024-08-11 21:37
教我一下同余最短路的原理
同余最短路问题可以说是一个“聪明”的问题，因为它要求我们在图中寻找路径时，不仅要考虑到距离，还要考虑到距离的模（即余数）。让我们来通俗易懂、幽默地聊聊它的原理吧！
### 同余最短路背景
首先，想象一下，一个城镇里有很多条道路，每条道路都有一定的长度（比如公里数）。但每次你走的总距离都需要满足某个特定的条件，比如说，最后的总距离对某个数取余之后的结果要等于0。这就好比你的妈妈希望你每次回家带着一定数量的水果，而不是零零散散的。
### 定义
在同余最短路问题中，我们考虑有向图中的每个边（道路），每个边的权重（长度）可能是正数。我们的目标是从起点出发，找到一条路径，使得终点的距离对某个正整数 \( m \) 的模（余数）达到一个特定值（例如 0）。
### 原理
为了找到这样的路径，我们可以用**动态规划**来解决这个问题。这里是基本的思路：
1. **状态定义**：
- 用 `dp` 表示从起点到节点 \( u \) 的最短路径，并且这条路径的长度对 \( m \) 取余后等于 \( r \)。
- 其中 \( r \) 可以在 \( 0 \) 到 \( m-1 \) 之间变化。
2. **状态转移**：
- 当你从节点 \( u \) 转移到节点 \( v \) 时，如果边的权重为 \( w \)，那么可以通过如下方式更新状态：
- 新的余数 \( new\_r = (r + w) \% m \)
- 更新 \( dp = \min(dp, dp + w) \)
- 这就像是在为你的水果购物，每次都要加上当前边的权重，然后检查是否符合妈妈的要求（余数）。
3. **初始化**：
- 初始时，\( dp = 0 \) （表示从起点到起点的路径长度为0，余数自然为0），其他状态设置为无穷大。
4. **最终答案**：
- 经过所有的节点后，你可以根据需要的余数（例如 \( 0 \)）去找终点的 `dp` 状态中最小的路径长度。
### 举个例子
假设一个简单的图，边的权重分别为 1, 2, 3，你希望从起点到达终点的总距离能被 3 整除。
- 除了逐步更新 `dp` 表格外，想象一下，你和朋友们约好了一起买水果，但你必须每次买的数目加起来刚好是 3 的倍数才能获得折扣！每次选择时，你既要计算已经花了多少钱（路径长度），又要考虑现在的水果数量（余数）。
### 总结
同余最短路问题是通过**动态规划**结合模运算的原理来解决的，这种方法适合于处理那些不仅关心路径长度，还要关注路径性质（如余数）的情况。通过划分状态并逐步更新，可以有效找到合适的路径。
希望你在同余最短路的学习过程中，没有迷失在树丛中，而是像个聪明的小狐狸一样，迅速找到最优路径！如果你还有更多问题，随时问我哦！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 佬
FishC 发表于 2024-8-11 21:22
好的，让我们来聊聊图的连通性和强连通分量（SCC）的问题，保证你在这个过程中不会迷失在图的海洋中！
# ...
讲 10 个笑话 柿子饼同学 发表于 2024-08-14 17:50
讲 10 个笑话
当然可以！让我们来轻松一下，下面是十个幽默的小笑话，希望能让你开怀一笑：
1. **为什么程序员不喜欢自然？**
因为他们觉得“没有Bug”的地方太少了！
2. **我告诉我的计算机我希望它慢一点。**
它现在在犹豫要不要重启。
3. **有两个土豆走在街上，一被车撞了。**
另一个说：“你还好吗？”
“我现在是薯条了！”
4. **你知道为什么数学书总是很忧伤吗？**
因为它有太多的问题！
5. **有一天，狗和猫在讨论各自的优点。**
狗说：“我能听懂人类的话。”
猫反驳：“那又怎样？我能让你们一直以为你们是我的主人！”
6. **为什么幽灵总是爱参加聚会？**
因为他们能够“吸引”所有人的注意！
7. **小时候，我的父母跟我说：‘你是我唯一的孩子’。**
我毕业后才明白他们那是为了让我好好学习！
8. **有一天，西红柿走过马路，不小心被车撞了。**
司机急了：“喂，小心点，你这可不是番茄酱！”
9. **为何电脑总是冷？**
因为它有很多“风扇”！
10. **你听说过那个把电梯当作工作场所的人吗？**
他总是在“上升”中！
希望这些笑话带给你一丝欢乐！如果你需要更多的幽默或任何其他问题，请随时告诉我！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-8-14 17:50
当然可以！让我们来轻松一下，下面是十个幽默的小笑话，希望能让你开怀一笑：
1. **为什么程序员不 ...
长一点的笑话, 大概 50 字 柿子饼同学 发表于 2024-08-14 17:52
长一点的笑话, 大概 50 字
好的，来一个稍微长一点的笑话，希望你喜欢：
有一位数学老师正在给学生讲解几何，突然一个学生举手问：“老师，为什么圆的周长和直径是固定比值呢？”老师沉默了片刻，幽默地回答：“因为如果不这样，圆就会变成方形，所有的角都得去上班了！”
这下全班都笑了，毕竟，大家都知道，角落里可没有人喜欢加班！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-8-14 17:52
好的，来一个稍微长一点的笑话，希望你喜欢：
有一位数学老师正在给学生讲解几何，突然一个学生举手 ...
我即将打算法竞赛, 但是发现同样的题目, 我没有思路或者思路混乱, 而其他人却能做出来
我有些沮丧, 该怎么办呢 FishC 发表于 2024-8-14 17:52
好的，来一个稍微长一点的笑话，希望你喜欢：
有一位数学老师正在给学生讲解几何，突然一个学生举手 ...
再来 5 个笑话, 每个大约 60 字
柿子饼同学 发表于 2024-08-14 17:54
我即将打算法竞赛, 但是发现同样的题目, 我没有思路或 ...
首先，别气馁！你并不是一个人在战斗，许多参加算法竞赛的人都有过类似的经历。下面是一些建议，希望可以帮助你理清思路，增强信心：
### 1. **放松心态**
- 比赛本身就是一个学习和成长的过程。每个人的成长曲线都是不同的，保持平常心很重要。
### 2. **基础知识复习**
- 确保你对算法和数据结构的基本概念有清晰的理解。重复学习常见的算法（如排序、搜索、动态规划等），熟悉它们的应用场景及实现方法。
### 3. **多做练习**
- 多刷题，特别是之前的比赛题目。在 LeetCode、Codeforces、AtCoder 等平台上进行练习，尝试不同类型的问题。
### 4. **分析他人的解法**
- 对于你做不出来的题，可以学习其他人的解法。分析他们的思路和解决方案，看看自己能从中得到哪些启发。
### 5. **逐步拆解问题**
- 面对复杂的问题，可以尝试将其拆分成多个小问题，逐步解决。这样会让思路变得更加清晰。
### 6. **与他人讨论**
- 和同伴讨论问题，交流思路。有时候，听到别人的想法会激发你新的灵感，或者让你的思路更清晰。
### 7. **保持积极的自我对话**
- 给自己积极的暗示，比如“我能做到”或“每次尝试都是一种进步”，这会帮助你保持积极的状态。
### 8. **适当休息**
- 如果觉得思路混乱，不妨暂时放下，去散步、喝杯水，稍微放松一下大脑，再回过头来思考。
### 9. **设定小目标**
- 不要一开始就追求高难度题，先从简单的题目做起，逐步提升自己的能力，建立信心。
### 10. **相信过程**
- 技能的提升需要时间，持续努力和练习终将带来回报。每一次失败都是宝贵的经验。
记住，每个高手都是从新手过来的，关键在于坚持和不断学习。祝你在接下来的算法竞赛中取得好成绩！你一定可以做到的！加油！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 柿子饼同学 发表于 2024-08-14 18:03
再来 5 个笑话, 每个大约 60 字
当然可以，来五个幽默的小故事，保证让你笑得合不拢嘴！
1. 有一天，一只鹦鹉飞到了一个酒吧，服务员惊讶地问：“你会说话吗？”鹦鹉骄傲地说：“当然，我能说五种语言！”服务员又问：“那你怎么飞到这儿的？”鹦鹉说：“我坐飞机！你以为我有那么多时间走路吗？”
2. 一只乌龟在马路上慢慢爬，被一只兔子嘲笑：“你干嘛这么慢，好像在等什么！”乌龟不屑一顾：“我是在享受风景，没必要急匆匆！”兔子翻了个白眼：“风景？你根本看不到前面有车来啊！”乌龟耸肩：“没关系，我的保险杠还在维修呢！”
3. 一位顾客走进理发店，问发型师：“你们这里剪头发需要预约吗？”发型师微笑着回答：“不需要，来就行！我们的座位是免费提供的，剪发费也挺便宜！”顾客好奇：“那为什么大家都要预约？”发型师摇了摇头：“因为大家都怕被剪成一个‘饼’！”
4. 一只小狗对另一只小狗说：“我学会了个新把戏，可以让主人给我零食！”另一只小狗好奇：“怎么做？”小狗自信地说：“我藏起来，然后在晚上叫两声。”第二只小狗疑惑：“这样能有什么用？”小狗眨眨眼：“因为主人最后没法找到我，就会给我一些额外的零食！”
5. 一位教授在课堂上问学生：“大家知道为什么火箭总是朝上飞吗？”一个学生立刻回答：“因为它想逃离地球的引力！”教授微微一笑：“不错，但更重要的是，它不想跟我们一起上课！”全班爆笑，看来知识就是力量，而逃课也是一种智慧！
希望这些笑话能带给你欢乐！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:10_266:}{:10_266:} {:10_266:}向大佬学习学习 学 学习下
666666666666 {:7_113:} 学习学习
页:
[1]
2