本文主要是介绍hdu 1102 uva 10397（最小生成树prim），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu 1102:
题意：
给一个邻接矩阵，给一些村庄间已经修的路，问最小生成树。
解析：
把已经修的路的权值改为0，套个prim（）。
注意prim 最外层循坏为n-1。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);int n;
int g[maxn][maxn];int prim()
{bool vis[maxn];int dis[maxn];memset(vis, false, sizeof(vis));memset(dis, inf, sizeof(dis));vis[1] = true;dis[1] = 0;int res = 0;int mark = 1;for (int i = 1; i <= n - 1; i++)///mark = 1 so n - 1{for (int j = 1; j <= n; j++){if (!vis[j] && g[mark][j] < dis[j])dis[j] = g[mark][j];}int mindis = inf;for (int j = 1; j <= n; j++){if (!vis[j] && dis[j] < mindis){mindis = dis[j];mark = j;}}vis[mark] = true;res += mindis;}return res;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (~scanf("%d", &n)){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){scanf("%d", &g[i][j]);}}int q;scanf("%d", &q);while (q--){int u, v;scanf("%d%d", &u, &v);g[u][v] = g[v][u] = 0;}printf("%d\n", prim());}return 0;
}
uva 10397:
基本上是一样的题目。。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 750 + 10;
const int inf = sqrt(2 * 20000 * 20000) + 10;int n;
double g[maxn][maxn];
double x[maxn], y[maxn];double dist(double x1, double y1, double x2, double y2)
{return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}double prim()
{double dis[maxn];bool vis[maxn];for (int i = 0; i <= n; i++){dis[i] = inf;vis[i] = false;}dis[1] = 0.0;vis[1] = true;double res = 0.0;int mark = 1;for (int i = 1; i <= n - 1; i++){for (int j = 1; j <= n; j++){if (!vis[j] && g[mark][j] < dis[j])dis[j] = g[mark][j];}double mindis = inf;for (int j = 1; j <= n; j++){if (!vis[j] && dis[j] < mindis){mindis = dis[j];mark = j;}}vis[mark] = true;res += mindis;}return res;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (~scanf("%d", &n)){for (int i = 1; i <= n; i++){scanf("%lf%lf", &x[i], &y[i]);}for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){g[i][j] = g[j][i] = dist(x[i], y[i], x[j], y[j]);}}int q;scanf("%d", &q);for (int i = 0; i < q; i++){int u, v;scanf("%d%d", &u, &v);g[u][v] = g[v][u] = 0;}
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= n; j++)
// {
// printf("%.2lf ", g[i][j]);
// }
// printf("\n");
// }printf("%.2lf\n", prim());}return 0;
}
这篇关于hdu 1102 uva 10397（最小生成树prim）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
