asdf

02321736m · 发布于 2024-08-17 · 浏览 481 回复 0

include <bits/stdc++.h>

define inf 0x3f3f3f3f

using namespace std; int g[200][200]; int vis[200], dis[200]; int n, m;

void prim(int v) {

vis[v] = 1;
dis[v] = 0;
for (int x = 1; x <= n; x++) {
	int min = inf;//把min初始化为极大值
	for (int y = 1; y <= n; y++) {
		if (vis[y] == 0 && dis[y] < min) {
			min = dis[y];
			v = y;
		}
	}
	vis[v] = 1;
	for (int y = 1; y <= n; y++) {
		if (vis[y] == 0 && dis[y] > g[v][y] && g[v][y] != 0)//判断节点y是否加入最小生成树
			dis[y] = g[v][y];
	}
}

}

int main() {

int w;
memset(g, 0, sizeof(g));
memset(vis, 0, sizeof(vis));
memset(dis, inf, sizeof(dis));
cin >> n >> m;
for (int x = 1; x <= m; x++) {
	int u, v, w;
	cin >> u >> v >> w;
	g[u][v] = g[v][u] = w;
}
prim(1);
int ans = 0;
cin >> w;
for (int x = 1; x <= n; x++)
	ans += dis[x];
cout << ans << ' ' << ans *w;
return 0;

}

全部回复 共 0 条

还没有人回复。往下写第一条。

发表回复