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

· · 题解

本人小蒟蒻，这是我的第一篇题解。希望管理员大大给过。

先按照权值 c_i 从小到大排序加入边，显然加边的目的是让 l_i\sim r_i 联通。首先最开始至少需要连一条边至 l_i 来保证新岛屿联通。如果 l_i 和 l_i+1 不联通，那么需要往 l_i+1 连一条边。否则需要找到第一个 x 和 x+1 不联通的位置，往 x+1 连一条边。如此循环往复寻找，连完即可。

用并查集维护：f_i 表示从 i 开始，i\sim f_i 全部联通。那么上述的操作就好办了，一直调用并查集的 find 函数查找最长连续段，因为每个点最多会被连一次，之后 find 函数直接跳过了，则复杂度为 O(n\alpha (n))。

献上本蒟蒻弱弱的代码，大佬轻喷：

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