样例没过,大佬求调
查看原帖
样例没过,大佬求调
755173
jkq2009楼主2024/11/28 07:52
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 200010;
struct Node {
	int x, y, v, idx;
	bool operator < (const Node &A) const {
		return v < A.v;
	}
} a[N];
struct Edge {
	int y, v;
	Edge(int _y, int _v) {
		y = _y, v = _v;
	}
};
int n, m, dist[N], f[N][21], g[N][21], fa[N];
ll res, ans[N];
vector<Edge> edge[N];

inline void dfs(int x) {
	for (auto i : edge[x])
		if (!dist[i.y]) {
			dist[i.y] = dist[x] + 1;
			f[i.y][0] = x;
			g[i.y][0] = i.v;
			dfs(i.y);
		}
}

int findset(int i) {
	if (i == fa[i])
		return i;
	return fa[i] = findset(fa[i]);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].v);
		a[i].idx = i;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	for (int i = 1; i <= m; i++) {
		int x = findset(a[i].x), y = findset(a[i].y);
		if (x != y) {
			res += a[i].v;
			edge[a[i].x].push_back(Edge(a[i].y, a[i].v));
			edge[a[i].y].push_back(Edge(a[i].x, a[i].v));
			fa[x] = y;
		}
	}
	dist[1] = 1;
	dfs(1);
	for (int i = 1; i <= 20; i++)
		for (int j = 1; j <= n; j++) {
			f[j][i] = f[f[j][i - 1]][i - 1];
			g[j][i] = max(g[j][i - 1], g[f[j][i - 1]][i - 1]);
		}
	for (int i = 1; i <= m; i++) {
		int x = a[i].x, y = a[i].y;
		if (dist[x] < dist[y])
			swap(x, y);
		int z = dist[x] - dist[y];
		int num = 0;
		for (int i = 0; z; z >>= 1, i++)
			if (z & 1) {
				num = max(num, g[x][i]);
				x = f[x][i];
			}
		if (x != y)  {
			for (int i = 20; i >= 0; i--)
				if (f[x][i] != f[y][i]) {
					num = max({num, g[x][i], g[y][i]});
					x = f[x][i];
					y = f[y][i];
				}
			num = max({num, g[x][0], g[y][0]});
		}
		ans[a[i].idx] = res - num + a[i].v;
	}
	for (int i = 1; i <= m; i++)
		printf("%lld\n", ans[i]);
	return 0;
}
2024/11/28 07:52
加载中...