社区讨论

求大佬查错,只剩下最后一个点

P2573[SCOI2012] 滑雪参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi86jb6q
此快照首次捕获于
2025/11/21 09:26
4 个月前
此快照最后确认于
2025/11/21 09:26
4 个月前
查看原帖
CPP
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
// WARNING
#define int long long
//#define char unsigned char
// WARNING
/*
應曆三十一日代碼
*/
#define F(x, y, z) for (int x = y; x <= z; x++)
#define D(x, y, z) for (int x = y; x >= z; x--)
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define cint const int &
#define cauto const auto &
#define pause                                                                  \
  while (1)                                                                    \
    ;
//#if __cplusplus < 201103L
//#error your compiler smells like shit!
//#error Shit!Shit!Shit!
//#endif
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = (static_cast<int>(1e5) + 25);
inline int read() {
  int c = getchar(), x = 0, y = 1;
  while (c > '9' || c < '0') {

    if (c == '-') {
      y = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * y;
}
inline char getc() {
  int c = getchar();
  while (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '#' ||
           c == '.')) {
    c = getchar();
  }
  return static_cast<char>(c);
}
static int n, m, height[MAXN];
struct road {
  int to, dis, nxt;
  road(int to = 0, int dis = 0, int nxt = 0) : to(to), dis(dis), nxt(nxt) {}
} static edge[MAXN * 10];
static int head[MAXN], tot = 0, ance[MAXN];
inline int getf(int x) {
  if (ance[x] == x) {
    return x;
  }
  return ance[x] = getf(ance[x]);
}
inline void add_road(int from, int to, int dis) {
  edge[++tot].to = to;
  edge[tot].dis = dis;
  edge[tot].nxt = head[from];
  head[from] = tot;
}
struct node {
  int from, to, dis;
  node(int from = 0, int to = 0, int dis = 0) : from(from), to(to), dis(dis) {}
  bool operator<(const node &right) {
    if (height[to] == height[right.to]) {
      return dis < right.dis;
    } else {
      return height[to] > height[right.to];
    }
  }
};
static bool vis[MAXN];
static vector<node> side;
static int ans = 0;
inline void dfs(int x) {
  vis[x] = true;
  ans++;
  for (int i = head[x]; i; i = edge[i].nxt) {
    side.push_back(node(x, edge[i].to, edge[i].dis));
    if (vis[edge[i].to]) {
      continue;
    }
    dfs(edge[i].to);
  }
}
signed main() {
  n = read();
  m = read();
  F(i, 1, n) {
    height[i] = read();
    ance[i] = i;
  }
  F(i, 1, m) {
    int from = read(), to = read(), dis = read();
    if (height[from] < height[to]) {
      swap(from, to);
    }
    add_road(from, to, dis);
    //    side.push_back(node(from, to, dis));
  }
  dfs(1);
  sort(all(side));
  int dis = 0;
  F(i, 0, side.size() - 1) {
    int ff = getf(side[i].from), ft = getf(side[i].to);
    if ((ff != ft)) {
      ance[ff] = ft;
      dis += side[i].dis;
    }
  }
  printf("%lld %lld", ans, dis);
  return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...