社区讨论
求大佬查错,只剩下最后一个点
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 条回复,欢迎继续交流。
正在加载回复...