Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 39820 | Accepted: 16192 |
Description
Input
Output
Sample Input
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
Sample Output
28
Source
Slyar:简单介绍一下题意。农民要建立互联网络,目的使村庄里所有的农民连上网,并且总费用最小。多组数据,每组数据给出一个n,然后给出n * n大小的无向图的邻接矩阵表示,值表示边权。要求输出最小生成树的权值和。
可以用Kruskal算法解决该题,用并查集检查待加入生成树的两边是否会构成回路,快速排序按权值排列边。
这里有一个优化:因为是无向图,所以矩阵是对称的,因此我们只保存上三角矩阵即可。这样到最后k的值就是边数,由循环n*n次缩减到循环k次...#include <iostream> #include <algorithm> #include <cstdio> using namespace std; #define M 101 #define INF 1000001 int map[M][M]; int n; int Prim() { int s=1; int m=1; bool cmp[M]={0}; //标记这个点是否在子图内。 cmp[s]=1; //从第一个点开始。 int min_w; //用来找当前的最小权边。 int prim_w=0; //用来存线路的总长。 int point; //这是用来存那个即将入图的那个点的。 int low_dis[M]; //这个用来存子图到这个点的最短距离。(关键) for(int i=1;i<=n;i++) low_dis[i]=INF; //初始化一定要大。 while(1) { if(m==n) break; //如果每个点都入图,已经将所有点连好了。 min_w=INF; for(int i=2;i<=n;i++) { if(!cmp[i] && low_dis[i]>map[s][i]) low_dis[i]=map[s][i]; //如果子图有更短的才替换(关键) if(!cmp[i] && min_w>low_dis[i]) { min_w=low_dis[i]; point=i; //这就是找那个最小权边,并标记它的下标。 } } s=point; cmp[s]=1; //这个点入图,加上权边值。 prim_w+=min_w; m++; //子图中的点数+1. } return prim_w; } int main() { int i,j; while(cin>>n) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>map[i][j]; cout<<Prim()<<endl; } return 0; }我也没办法。。。模板就这样。。。
POJ 1258 Agri-Net (最小生成树+Prim),布布扣,bubuko.com
POJ 1258 Agri-Net (最小生成树+Prim)
原文:http://blog.csdn.net/qq2256420822/article/details/38371383