汤姆大人我的神 • 3个月前
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;
}
评论:
请先登录,才能进行评论