asdf

汤姆大人我的神  •  3个月前


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;

}


评论:

请先登录,才能进行评论