[心之碎片] - 20240803模拟赛
总结与反思{:10_277:}A - 数据结构维护前缀和要提前加一个 0, 不然 1 是取不到的
C - 最小生成树相关问题两种思考: 按照边权分类 或者 建一个树然后树剖加边
D - 思考问题先想降维的情况, 本题的思路就是由 l == r 的情况想出来的
C - 又见最小生成树
现在给出一幅个节点条边的无向连通图, 请判断原图中的每条边是否一定在最小生成树中
对于每条边 :
如果这条边一定出现在任意一棵最小生成树中, 输出 1
如果一定不会出现在最小生成树中, 输出 2
如果无法确定, 输出 0{:10_266:}
最小生成树问题我们一般想到按照边权分类, 同边权的一起考虑
这里有一个建图技巧就是 *2 + 1
假设前面的边都加进去, 现在有一些边连接这些连通块
如果是割边, 就一定经过
如果在连通块里面, 由于连通块里面的边都比现在的边小, 所以一定不经过
剩下的是可能的
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 5;
struct Edge {
int u, v, w, id;
} e;
int n, m, ans;
struct DSU {
int pa;
DSU() {
for (int i = 1; i < N; i++) pa = i;
}
int Find(int x) {
if (x == pa)
return x;
return (pa = Find(pa));
}
void Merge(int x, int y) { pa = y; }
} dsu;
// 每次循环新建图和加入的点
vector<int> point;
vector<pii> g;
int dfn, low, tot;
void Tarjan(int u, int eid) {
dfn = low = ++tot;
for (auto ed : g) {
int v = ed.first;
if (!dfn) {
Tarjan(v, ed.second);
low = min(low, low);
// 如果这个新边是割边, 就必须经过
if (dfn < low) {
ans = 1;
}
} else if ((eid >> 1) != (ed.second >> 1)) {
low = min(dfn, low);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("mstagain.in", "r", stdin);
freopen("mstagain.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
e = { u, v, w, i };
}
sort(e + 1, e + m + 1, [](Edge& a, Edge& b) { return a.w < b.w; });
for (int i = 1; i <= m; i++) {
// 找出权值相等的区间
int l = i, r = i;
while (r <= m && e.w == e.w) r++;
r--;
// Kruskal
for (int j = l; j <= r; j++) {
int u = dsu.Find(e.u), v = dsu.Find(e.v);
if (u == v) {
// 已经成连通块了, 里面的任何边都小于现在的权值, 一定不取
ans.id] = 2;
continue;
}
// 如果没成就连边(新图)
point.emplace_back(u);
point.emplace_back(v);
// 编号小技巧轻松判断反边, 更新答案也好
g.emplace_back(v, e.id << 1);
g.emplace_back(u, e.id << 1 | 1);
}
for (auto j : point) {
if (!dfn)
Tarjan(j, 0);
}
for (int j = l; j <= r; j++) {
int u = dsu.Find(e.u), v = dsu.Find(e.v);
// 把所有边权一样的边都连起来, 变成新的图
if (u == v)
continue;
dsu.Merge(u, v);
}
// 清零等着复用
for (auto j : point) {
g.clear();
dfn = low = 0;
}
point.clear();
tot = 0;
i = r;
}
for (int i = 1; i <= m; i++) {
cout << ans << '\n';
}
return 0;
}
D - 排列
给你 n 个点, 有点权
你需要构造一个排列, 使得最终的满足条件的点的权值之和最大
每个点都有一个前置区间 , 表示如果范围内的某个点排在 i 的前面了，那么 i 点的权值就要被累加进去
应该如何排列, 使得点权和才能最大{:10_245:}
当 n <= 20 时, 可以状压 dp 拿 30 分
接下来考虑 l == r 的情况 (先考虑一维的问题) , 发现本质上是区间内的点向 i 连边
在一个 scc 中, 每个点都可以互通, 所以权值都可以加, 入度为 0 的 scc 需要牺牲一个最小的权值当作第一个数, 后面的都能加
然后区间的连边需要线段树优化建图
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
const int M = 1e5 + 5;
vector<int> e;
int n, ans, val;
struct SGT {
#define lc u << 1
#define rc u << 1 | 1
int tot, t;
void Build(int u, int l, int r) {
if (l == r) {
t = l;
return;
}
int mid = (l + r) >> 1;
Build(lc, l, mid);
Build(rc, mid + 1, r);
t = ++tot;
e].emplace_back(t);
e].emplace_back(t);
}
void Modify(int u, int l, int r, int ql, int qr, int to) {
if (ql <= l && r <= qr) {
e].emplace_back(to);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid)
Modify(lc, l, mid, ql, qr, to);
if (qr > mid)
Modify(rc, mid + 1, r, ql, qr, to);
}
} sgt;
int dfn, low, tot;
int stk, top;
int scc, bel, minv, din;
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;
if (v <= n)
minv = min(minv, val);
} while (v != u);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("permutation.in", "r", stdin);
freopen("permutation.out", "w", stdout);
cin >> n;
sgt.tot = n;
sgt.Build(1, 1, n);
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r >> val;
ans += val;
sgt.Modify(1, 1, n, l, r, i);
}
memset(minv, 0x3f, sizeof(minv));
for (int i = 1; i <= sgt.tot; i++) {
if (!dfn)
Tarjan(i);
}
// 入度
for (int i = 1; i <= tot; i++) {
for (auto j : e) {
if (bel != bel) {
din]++;
}
}
}
// 前面没有人, 必须牺牲一个最小值
for (int i = 1; i <= scc; i++) {
if (!din)
ans -= minv;
}
cout << ans;
return 0;
} 这段代码是在处理最小生成树（MST）中的边的判断问题。换句话说，给定一张无向连通图，我们需要判断每条边是否一定在任何一棵最小生成树中。这是一个典型的图论问题，我们可以通过以下几点来理解它，带点幽默感哦：
1. **边的分类**：首先，当我们面临一个众多边的图时，就像在一个派对上，所有的朋友都在聊天。我们可以按照“边权”来分类，低价位边在一块，高价位边在另一块。这样，有助于我们更清晰地分析每条边的重要性。就像你在选择餐馆时，会先查查菜单上的价格一样。
2. **割边的重要性**：如果这条边是一个割边（也称为桥），那么它是连接两个不同的连通部分的关键。如果你把它剪断，图就成两半了，因此这条边一定出现在最小生成树中。就像是你在居家办公时，家里Wi-Fi信号是多么的关键，没了它你就变成孤岛。
3. **连通块内的边**：如果一条边在连通块内，那么它可能是不必要的，因为该块内部的其他边都比它便宜，最小生成树自然会选择那些更便宜的。想象一下，一个派对上，你已经有了免费饮料，谁还要去买贵的鸡尾酒呢？
4. **不确定边**：最后，还有一些边是无法确定的，像是一张悬疑片的剧情一样复杂。对于这些边，如果没有足够的信息我们就只能输出0，表示不确定。这就像你在看电影时猜测反转情节，但仍然得留到结局才知道。
然后，代码实现的部分涉及如何通过并查集（DSU）和Tarjan算法来完成这些检测工作。该算法就像一位侦探，通过不断查找和合并，帮助我们判断各个边的位置和重要性。
总的来说，这道题考的是对图的理解和对算法的应用，就像是在料理比赛中，每一样食材都要搭配得当，才能做出最佳的菜肴！希望这番解析能帮到你，让你在最小生成树的世界里游刃有余！如果你还有什么问题，尽管问吧，准备好笑料，咱们继续聊！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:10_256:}加油 cy 学习一下 {:10_256:}{:10_256:} 加油 {:10_277:} {:10_257:} 加油 学习一下 {:7_113:} 👌 👌
页:
[1]