CodeVS/1078

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
最小生成树	★☆☆☆☆	答案正确	100	2015-7-22 20:08:48	无

题解

堆优化的Prim算法。具体看Wiki或代码注释吧。

代码

1078.cpp代码已折叠 展开折叠内容

显示/移除行号 #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; }