此题就是prim算法模板
直接给代码、
#include "iostream" using namespace std; #define MAXSIZE 102 int map[MAXSIZE][MAXSIZE]; int vis[MAXSIZE]; int temp[MAXSIZE]; int main() { int n; while (scanf("%d",&n)!=EOF) { int ans=0; int i,j; for (i=0;i<n;i++) { for (j=0;j<n;j++) { scanf("%d",&map[i][j]); } } memset(vis,0,sizeof(vis)); for (j=0;j<n;j++) { temp[j]=9000010; } i=0; for (j=0;j<n;j++) { if (map[i][j]!=0) if (map[i][j]<temp[j]) { temp[j]=map[i][j]; } } vis[0]=1; while (i<n-1) { //找最小的边 int min=9000010; int minindex=0; for (j=0;j<n;j++) { if (vis[j]==1) { continue; } if (min>temp[j]) { min=temp[j]; minindex=j; } } //把最小的边的顶点加入集合 vis[minindex]=1; //更新temp for (j=0;j<n;j++) { if (map[minindex][j]!=0&&vis[j]!=1) if (map[minindex][j]<temp[j]) { temp[j]=map[minindex][j]; } } ans+=min; i++; } printf("%d\n",ans); } return 0; } /* 6 0 6 1 5 0 0 6 0 5 0 3 0 1 5 0 5 6 4 5 0 5 0 0 2 0 3 6 0 0 6 0 0 4 2 6 0 */
相关推荐
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
北大POJ1789-Truck History【Prim】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ2485-Highways【Prim】 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ3414-Pots 解题报告+AC代码
POJ1523 - SPF 测试数据。 数据来源:Greater New York 2000 问题H
POJ1724-ROADS 测试数据。数据来源:CEOI 1998 Round II
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大ACM-POJ1010 - STAMPS 原比赛(Pacific Northwest 1998)题目的测试数据
北大POJ3020-Antenna Placement 解题报告+AC代码
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ1472-Instant Complexity 测试数据。数据来源:Southwestern European Regional Contest 1997
北大ACP-POJ 1035 - Spell checker 原比赛题目测试数据(问题G)
北大POJ中级-基本算法 解题报告+AC代码