文章

5

粉丝

10

获赞

5

访问

805

头像
继续畅通工程 题解:prim算法
P1311 浙江大学机试题
发布于2025年5月12日 22:47
阅读数 91

已经连通了的道路把权值设为0,意为不用再对此花费开销,在prim算法的正常处理过程中把这些边加入集合并累加权值时相当于进行一次空操作。

#include<bits/stdc++.h>
using namespace std;
int prim(vector<vector<int>> graph, int n) {
	vector<int> dis(n + 1, INT_MAX);
	vector<bool> visited(n + 1);
	dis[1] = 0, visited[1] = true;
	for (int i = 1; i <= n; i++)
		dis[i] = min(dis[i], graph[1][i]);
	int ans = 0;
	for (int i = 2; i <= n; i++) {
		int index = -1, temp = INT_MAX;
		for (int j = 1; j <= n; j++)
			if (!visited[j] && dis[j] < temp)
				index = j, temp = dis[j];
		ans += temp;
		visited[index] = true;
		for (int j = 1; j <= n; j++)
			dis[j] = min(dis[j], graph[index][j]);
	}
	return ans;
}
int main() {
	int n, u, v, w, f;
	while (cin >> n) {
		if (n == 0)
			break;
		vector<vector<int>> graph(n + 1, vector<int>(n + 1,INT_MAX));
		for (int i = 0; i < n * (n - 1) / 2; i++) {
			cin >> u >> v >> w >> f;
			if (f == 1)...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发