首页 > 代码库 > hdu1301&poj1251 Jungle Roads(最小生成树之prim果题)
hdu1301&poj1251 Jungle Roads(最小生成树之prim果题)
转载请注明出处:http://blog.csdn.net/u012860063
题目链接:
HDU:http://acm.hdu.edu.cn/showproblem.php?pid=1301
POJ: http://poj.org/problem?id=1251
一道prim算法的果题!
题目很长,这里就不贴题目了。
题意: 给你每个村庄之间的维护道路的费用,求最小的费用。
代码如下:
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define INF 0xfffffff #define N 147 int map[N][N]; int dis[N],vis[N]; //创建map二维数组储存图表,dis数组记录每2个点间最小权值. //vis[N]数组标记某点是否已访问 int min(int a, int b) { return a<b?a:b; } int prim(int n, int sta) { int i, j, k, MIN, sum = 0; for(i = 1; i <= n; i++)//第一次给dis数组赋值 { dis[i]=map[sta][i]; vis[i] = 0; } vis[sta] = 1;//从某点开始,分别标记和记录该点 for(i = 1; i < n; i++)//再运行n-1次 { MIN = INF; k = 0; for(j = 1; j <= n; j++) { if(vis[j]==0 && dis[j]<MIN)//找出最小权值并记录位置 { k = j; MIN = dis[j]; } } if(k != 0) { vis[k] = 1; //标记该点 sum+=dis[k];//最小权值累加 for(j = 1; j <= n; j++)//更新权值 { dis[j] = min(map[k][j],dis[j]); } } } return sum; } int main() { int n, i, j, k, m,t; char ch,tt; int sum; while(cin >> n && n) { for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) map[i][j]=INF; for(i = 1; i < n; i++) { cin>>ch>>m; for(j = 1; j <= m; j++) { cin>>tt>>t; //防止有重边出现 map[ch-'A'+1][tt-'A'+1]=min(map[ch-'A'+1][tt-'A'+1],t); map[tt-'A'+1][ch-'A'+1]=map[ch-'A'+1][tt-'A'+1]; } } sum = prim(n,1); cout<<sum<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。