题目1 : 最小生成树三·堆优化的Prim算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
回到两个星期之前，在成功的使用Kruscal算法解决了问题之后，小Ho产生了一个疑问，究竟这样的算法在稀疏图上比Prim优化之处在哪里呢？
输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。
接下来的M行，每行描述一条路线，其中第i行为3个整数N1_i, N2_i, V_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。
对于100%的数据，满足N<=10^5, M<=10^6，于任意i满足1<=N1_i, N2_i<=N, N1_i≠N2_i, 1<=V_i<=10^3.
对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。
输出
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
- 样例输入
-
5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185 - 样例输出
-
92
分析：之前弄了好长时间，看了好多材料也没搞懂怎么优化prim。今天在操作系统课上，不小心走神了。于是乎，只花了几分钟就想
出来了到底要怎么优化。之前看别人的博客什么的，感觉很复杂。现在把我的想法写出来：
堆优化prim算法：首先我们先想，之前在写prim的时候需要这样做，从当前的生成树开始，遍历所有可以抵达当前生成树的边，找到
一条最短的边，将该边的权值加到生成树的权值总和上，加该点标记访问，并加到生成树上来。现在如果我们可以优化方法找到那条最
短边的话，那复杂度不就降低了。怎么优化呢？之前的做法是用一个数组保存每个节点到生成树的距离，每次找的过程都要遍历一次这
个数组。现在我们用一个优先队列（小根堆）来保存所有可以抵达生成树的边，每次只要取出该队列的最前面的且合法的边加到生成树
上来就醒了。不合法的边会在这个过程中丢弃！
有图有文字的描述过程如下：代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define LL long long int
#define N 100000+10 //最大节点数
#define M 1000000+10 //最大的边数
#define MOD 142857
//N<=10^5, M<=10^6 using namespace std;
int n, m;
struct node
{
int v, w;
bool operator<(const node &dd)const{
return w>dd.w;
} //权值小的优先
};
vector<node>q[N];
bool vis[N];
//堆优化的prim算法
LL ans; void queue_prim()
{
//以节点1为起点进行扩展安全边 生成最小树
priority_queue<node>que;
while(!que.empty())
que.pop(); //初始化清空优先队列 维护一个小根堆
//这样每次找安全边的速度就提高了
ans = 0;
memset(vis, false, sizeof(vis));
for(int i=0; i<q[1].size(); i++){
que.push(q[1][i]); //将起点的所有连接边全部加入队列中来
}
vis[1]=true;
int edge=n-1;//边数
node cur;
while(edge--)
{
cur = que.top();
que.pop();//这个地方需要注意一下
//并不是每个从优先队列取出来的边都是可以加到生成树上去的 if(vis[cur.v]==true){
while(vis[cur.v]){
cur=que.top(); que.pop();
}
}
ans = ans+cur.w; //printf("%d-- ", cur.w );
vis[cur.v]=true; //加入生成树的该点将被标记访问
for(int i=0; i<q[cur.v].size(); i++){
if(vis[ q[cur.v][i].v ]==false) //当前加入生成树的点可以扩充出的边指向的节点
que.push(q[cur.v][i]);//如果没有被访问才会加入到队列当中来
}
}
} int main()
{
scanf("%d %d", &n, &m);
int i, j;
int u, v, w;
node cur;
for(i=0; i<=n; i++)
q[i].clear(); for(i=0; i<m; i++)
{
scanf("%d %d %d", &u, &v, &w);
cur.v=v; cur.w=w;
q[u].push_back(cur);
cur.v=u;
q[v].push_back(cur); //建立双向边
}
queue_prim();
printf("%lld\n", ans );
return 0;
}