#4 WA (Kruskal)
查看原帖
#4 WA (Kruskal)
109442
pV_equals_nRT楼主2023/10/23 15:14
#include <bits/stdc++.h>
using namespace std;

struct edge {
	int u, v;
	long long w;
	bool operator < (const edge &x) const {
		return x.w < w;
	}
};

const int M = 2005;
int n, c[M], k[M], xi[M], yi[M], fa[M];
long long sum;
priority_queue <edge> q;
int ai, bi;
int a[M];
vector <edge> b;

int find(int x) {
	return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		fa[x] = y;
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &xi[i], &yi[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &k[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			long long t = (k[i] + k[j]) * (abs(xi[i] - xi[j]) + abs(yi[i] - yi[j]));
			q.push({i, j, t});
		}
	}
	for (int i = 1; i <= n + 1; i++) {
		fa[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		q.push({i, n + 1, c[i]});
	}
	while (!q.empty()) {
		edge t = q.top();
		q.pop();
		if (find(t.u) != find(t.v)) {
			merge(t.u, t.v);
			sum += t.w;
			if (t.u == n + 1 || t.v == n + 1) {
				ai++;
				a[ai] = t.u == n + 1 ? t.v : t.u;
			} else {
				bi++;
				b.push_back({t.u, t.v, 0});
			}
		}
	}
	printf("%d\n", sum);
	printf("%d\n", ai);
	for (int i = 1; i <= ai; i++) {
		printf("%d ", a[i]);
	}
	printf("\n%d\n", bi);
	for (int i = 0; i < bi; i++) {
		printf("%d %d\n", b[i].u, b[i].v);
	}
}

样例过了,但是CF上第四个点WA了

2023/10/23 15:14
加载中...