本文主要是介绍poj 1287 Networking（prim or kruscal最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意给你点与点间距离，求最小生成树。
注意点是，两点之间可能有不同的路，输入的时候选择最小的，和之前有道最短路WA的题目类似。
prim代码：
#include<stdio.h>const int MaxN = 51;
const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];
int P;int prim()
{bool vis[MaxN];int dis[MaxN];int res = 0;for(int i = 1; i <= P; i++){dis[i] = INF;vis[i] = false;}dis[1] = 0;vis[1] = true;int mark = 1;for(int i = 1; i < P; i++){for(int j = 1; j <= P; j++){if(!vis[j] && dis[j] > g[mark][j])dis[j] = g[mark][j];}int mindis = INF;for(int j = 1; j <= P; j++){if(!vis[j] && mindis > dis[j]){mindis = dis[j];mark = j;}}vis[mark] = true;res += mindis;}return res;
}int main()
{//freopen("in.txt", "r", stdin);int R;while(scanf("%d", &P) && P){scanf("%d", &R);for(int i = 1; i <= P; i++){for(int j = 1; j <= P; j++){if(i == j)g[i][j] = 0;elseg[i][j] = INF;}}int x, y, w;for(int i = 1; i <= R; i++){scanf("%d%d%d", &x, &y, &w);if(g[x][y] > w){g[x][y] = g[y][x] = w;}}int ans = prim();printf("%d\n", ans);}return 0;
}
不用kruscal是因为我不知道边的数组应该开多大啊！
写了一个。
时间用得比prim少。
kruscal代码：
#include<stdio.h>
#include<algorithm>
using namespace std;const int MaxN = 51;
const int INF = 0x3f3f3f3f;int P, R;
int fa[MaxN];struct edge
{int x, y;int w;bool operator<(const edge &b)const{return w < b.w;}
}e[2500];int find(int x)
{if(x != fa[x])fa[x] = find(fa[x]);return fa[x];
}int kruscal()
{int res = 0;sort(e, e + R);for(int i = 1; i <= P; i++)fa[i] = i;for(int i = 0; i < R; i++){int t1 = find(e[i].x);int t2 = find(e[i].y);if(t1 != t2){fa[t2] = t1;res += e[i].w;}}return res;
}int main()
{while(scanf("%d", &P) && P){scanf("%d", &R);for(int i = 0; i < R; i++){scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);}int ans = kruscal();printf("%d\n", ans);}return 0;
}
这篇关于poj 1287 Networking（prim or kruscal最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
