UVa 10034 Freckles (MST 稠密图的O(V^2)的Prim算法)

本文主要是介绍UVa 10034 Freckles (MST 稠密图的O(V^2)的Prim算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

10034 - Freckles

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=975

纯模板题。

完整代码：

/*0.019s*/#include<bits/stdc++.h>
using namespace std;
const int mx = 105;double x[mx], y[mx], dis[mx][mx];
double disTo[mx]; /// 当前的MST到点j的最短距离
bool vis[mx];double findMST(int N)
{int p, i, j;double minn, cost = 0.0;memset(vis, 0, sizeof(vis));memcpy(disTo, dis, N * sizeof(double));for (i = 1; i < N; ++i){minn = DBL_MAX;for (j = 1; j < N; ++j)if (!vis[j] && disTo[j] < minn)p = j, minn = disTo[j]; /// 找到一条横切边vis[p] = true; /// 将横切边加到MST中cost += sqrt(minn);for (j = 1; j < N; ++j)if (!vis[j] && dis[p][j] < disTo[j])disTo[j] = dis[p][j]; /// 更新当前的MST到点j的最短距离}return cost;
}int main()
{int T, i, j, N;scanf("%d", &T);while (T--){scanf("%d", &N);for (i = 0; i < N; ++i) scanf("%lf%lf", &x[i], &y[i]);for (i = 0; i < N; ++i)for (j = 0; j < i; ++j)dis[j][i] = dis[i][j] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);printf("%.2f\n", findMST(N));if (T) putchar(10);}return 0;
}

这篇关于UVa 10034 Freckles (MST 稠密图的O(V^2)的Prim算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---