首页 > 代码库 > POJ 1258 Agri-Net
POJ 1258 Agri-Net
题目链接
http://poj.org/problem?id=1258
题目大意：
农民约翰竞选为了这个小镇的市长，他竞选的时候承诺要把他所管辖区域的所有地方的网络连接起来。当然他需要你的帮助，约翰需要一个可以快速到达所有农民的联通网，为了降低成本他想要最少的光纤来来连接其他的农场。
给你一个表，代表从一个农场到达另一个农场所需要的光纤花费，你要找出将所有农场连接起来的最小花费。每个农场都要连接起来， 我从一个农场可以到达其他任何一个农场，这里农场之间的距离不会超过 100000.
输入：
输入包含多个测试实例， 第一个一个 N 代表有N 个城镇， 然后是个 N*N 的邻接矩阵，
输出：
输出最小生成树。
题目分析：
明显的是求一个最小生成树，因为下面给的就是邻接矩阵， 所以我们用邻接矩阵写是最好不过了， 直接 Prime+ 邻接矩阵搞定
#include <iostream>#include <cmath>#include <cstring>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>using namespace std;#define INF 0xfffffff#define maxn 103struct Edge{ int e, w; Edge(int e=0,int w=0) : e(e), w(w) {}};int G[maxn][maxn];bool vis[maxn];int dist[maxn], n;int Prime(){ int sum = 0; dist[0] = 0; for(int i=0; i<n; i++) { int Min = INF, index; for(int j=0; j<n; j++) { if(!vis[j] && Min > dist[j]) index = j, Min = dist[j]; } sum += Min; vis[index] = true; for(int j=0; j<n; j++) { if(!vis[j] && dist[j] > G[index][j]) { dist[j] = G[index][j]; } } } return sum;}void Init(){ for(int i=0; i<n; i++) { vis[i] = false; dist[i] = INF; }}int main(){ while(cin >> n) { Init(); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { cin >> G[i][j]; } } int ans = Prime(); cout << ans <<endl; } return 0;}
POJ 1258 Agri-Net
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。