查看CodeVS/1078的源代码 ←CodeVS/1078

[[分类:最小生成树]]
==摘要==
{{信息题|最小生成树|http://www.codevs.cn/problem/1078/|1|100|time=2015-7-22 20:08:48}}
==题解==
堆优化的Prim算法。具体看Wiki或代码注释吧。
==代码==
{{折叠|1078.cpp代码已折叠
|<pre>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<set>
#include<iterator>
#include<queue>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<map>
#include<cstdlib>
using namespace std;
#define foreach(i,a) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)
#define v2 pair<int,int>
#define v3 pair<int, v2 >
#define x first
#define xx x
#define yy second
#define y yy.xx
#define z yy.yy
#define m2 make_pair
#define m3(a,b,c) make_pair(a,make_pair(b,c))
#define s(x) scanf("%d",&x)
int dis[1010][1010];//邻接矩阵//
void sp(v2 &p)
{
 s(p.xx);s(p.yy);
}
struct path//路径//
{
 int len;//长度//
 v2 FAT;//连接的点//
 friend bool operator<(path a, path b) { return a.len>b.len; }
 path() :len(0), FAT() {}
 path(int f, int t)
 {
  len = dis[f][t];
  FAT.xx = f;
  FAT.yy = t;
 }
};
set<int> r;//已经加入生成树的点集//
priority_queue< path  > x;//存放将要放入生成树的堆//
int main()
{
 int totalLen = 0;
 int n;
 //读入数据//
 s(n);
 for (int i = 1;i <= n;++i)
  for (int j = 1;j <= n;++j)
  {
   s(dis[i][j]);
  }
 //将与节点1相连的边插入堆//
 for (int i = 2;i <= n;++i)
  x.push(path(1, i));
 r.insert(1);//节点1放入生成树//
 
 while (r.size() != n&&!x.empty())//树非空//
 {
  path t = x.top();
  x.pop();
  bool ha = r.count(t.FAT.xx), hb = r.count(t.FAT.yy);
  int next = 0;
  if (!ha)next = t.FAT.xx;
  if (!hb)next = t.FAT.yy;
  if (next)
  {
   r.insert(next);//加入点//
   totalLen += t.len;
   for (int to = 1;to <= n;++to)
    if (!r.count(to))
     x.push(path(to, next));//相连路径加入堆//
  }
 }
 cout << totalLen << endl;
}

</pre>
|code1078}}