Prim最小生成树10分求助
查看原帖
Prim最小生成树10分求助
759274
Stevehim楼主2023/3/31 09:35

RT,WA8个点T1个.
思路是将所有点与其它点先建边然后跑Prim,然后就错了QAQ。代码如下

#include <bits/stdc++.h>
#define maxn 5010
using namespace std;
const int inf = 2147483647;

struct edge {
	int to;
	int nxt;
	double val;
} a[maxn];
int h[maxn];
bool vis[maxn];
double dis[maxn];
int cnt;
int tot; //记录几个点标记

void add(int from, int to, double val) {
	cnt++;
	a[cnt].to = to;
	a[cnt].val = val;
	a[cnt].nxt = h[from];
	h[from] = cnt;
}
int n, m;

struct Point {
	int x, y;
} point[maxn];

struct node {
	double dis;  //距离
	double pos; //结点的编号
	friend bool operator < (node a, node b) {
		return a.dis > b.dis;
	}
} tmp;
priority_queue<node> q; //优先队列
double ans; //记录边权

double get(int i, int j) {
	return (sqrt(abs(point[i].x - point[j].x) * abs(point[i].x - point[j].x) + abs(point[i].y - point[j].y) * abs(
	                 point[i].y - point[j].y)));
}

void prim() {
	for (int i = 1; i <= n; i++) {
		dis[i] = inf; //初始化
	}
	dis[1] = 0; //赋初值
	tmp.dis = 0;  //赋初值
	tmp.pos = 1; //赋初值
	q.push(tmp); //推入队列
	while (!q.empty()) {
		tmp = q.top();
		q.pop();
		int u = tmp.pos; //取出结点编号
		int d = tmp.dis; //取出结点距离
		if (vis[u]) { //访问过就返回
			continue;
		}
		tot++; //标记的点加一
		vis[u] = 1; //打上标记
		ans += dis[u]; //答案加上
		for (int i = h[u]; i; i = a[i].nxt) {
			int v = a[i].to;
			double w = a[i].val;
			if (dis[v] > w) { //与Dijkstra的松弛其实很想
				tmp.dis = dis[v] = w;
				tmp.pos = v;
				q.push(tmp);
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &point[i].x, &point[i].y);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				continue;
			add(i, j, get(i, j)); //建边
		}
	}
	prim();
	printf("%.2lf", ans);
	return 0;
}
2023/3/31 09:35
加载中...