poj 1258 Agri-Net（最小生成树模板代码）

本文主要是介绍poj 1258 Agri-Net（最小生成树模板代码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

感觉用这题来当模板更适合。

题意就是给你邻接矩阵求最小生成树啦。~

prim代码：效率很高。172k...0ms。

#include<stdio.h>
#include<algorithm>
using namespace std;const int MaxN = 101;
const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];
int n;int prim()
{bool vis[MaxN];int dis[MaxN];int res = 0;for(int i = 1; i <= n; i++){vis[i] = false;dis[i] = INF;}dis[1] = 0;vis[1] = true;int mark = 1;for(int i = 1; i < n ; i++){for(int j = 1; j <= n; j++){if(!vis[j] && dis[j] > g[mark][j]){dis[j] = g[mark][j];}}int mindis = INF;for(int j = 1; j <= n; j++){if(!vis[j] && mindis > dis[j]){mindis = dis[j];mark = j;}}vis[mark] = true;res += mindis;}return res;
}int main()
{while(scanf("%d", &n)!=EOF){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){scanf("%d", &g[i][j]);}}int ans = prim();printf("%d\n", ans);}return 0;
}

kruscal代码：效率偏低了，还WA了一发。252k...16ms

#include<stdio.h>
#include<algorithm>
using namespace std;const int MaxN = 101;int n, p;
int fa[MaxN];struct edge
{int x, y, w;bool operator<(const edge &b)const{return w < b.w;}
} e[MaxN * MaxN];int find(int x)
{if(fa[x] != x)fa[x] = find(fa[x]);return fa[x];
}int kruscal()
{int res = 0;sort(e, e + p);for(int i = 1; i <= n; i++)//！注意这个地方,根节点的存储。fa[i] = i;for(int i = 0; i < p; 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", &n)!=EOF){p = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){scanf("%d", &e[p].w);e[p].x = i;e[p].y = j;p++;}}int ans = kruscal();printf("%d\n", ans);}return 0;
}

这篇关于poj 1258 Agri-Net（最小生成树模板代码）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---