文章
5
粉丝
10
获赞
5
访问
805
已经连通了的道路把权值设为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)...
登录后发布评论
暂无评论,来抢沙发