专栏文章

P14548 [IO 2024 #3] 拯救波利尼西亚

ddonk2
P14548题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min48pdh
此快照首次捕获于
2025/12/01 20:18
3 个月前
此快照最后确认于
2025/12/01 20:18
3 个月前
查看原文
本人小蒟蒻，这是我的第一篇题解。希望管理员大大给过。
先按照权值 cic_i 从小到大排序加入边，显然加边的目的是让 li∼ril_i\sim r_i 联通。首先最开始至少需要连一条边至 lil_i 来保证新岛屿联通。如果 lil_i 和 li+1l_i+1 不联通，那么需要往 li+1l_i+1 连一条边。否则需要找到第一个 xx 和 x+1x+1 不联通的位置，往 x+1x+1 连一条边。如此循环往复寻找，连完即可。
用并查集维护：fif_i 表示从 ii 开始，i∼fii\sim f_i 全部联通。那么上述的操作就好办了，一直调用并查集的 find 函数查找最长连续段，因为每个点最多会被连一次，之后 find 函数直接跳过了，则复杂度为 O(nα(n))O(n\alpha (n))。
献上本蒟蒻弱弱的代码，大佬轻喷：
CPP
int n, m, p[N], res;
struct tt {
  int l, r, w;
}ed[N];

int find(int x) {
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}

signed main() {
  cin >> n >> m;
  rep(i, 1, m) cin >> ed[i].l >> ed[i].r >> ed[i].w;
  sort(ed + 1, ed + m + 1, [](tt x, tt y) {
    return x.w < y.w;
  });
  rep(i, 1, n) p[i] = i; 
  rep(i, 1, m) {
    int l = ed[i].l, r = ed[i].r, w = ed[i].w;
    res += w;
    if (find(l) >= r) continue;
    int tmp = l;
    while (1) {
      tmp = find(tmp);
      if (tmp >= r) break;
      res += w;
      int fx = find(tmp), fy = find(tmp + 1);
      p[fx] = fy;
      tmp++;
    }
  }
  int cnt = 0;
  rep(i, 1, n) if (find(i) == i) cnt++;
  if (cnt > 1) puts("-1");
  else cout << res << endl;
}
哎，提高组不理想的我该何去何从呢？NOIP 能拿下 400 吗？qwq

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...