(以“分类:最小生成树 ==摘要== {{信息题|最小生成树|http://www.codevs.cn/problem/1078/|1|100|time=2015-7-22 20:08:48}} ==题解== 堆优化的Prim算...”为内容创建页面) |
小 (分类) |
||
第1行: | 第1行: | ||
− | [[分类: | + | [[分类:生成树]] |
==摘要== | ==摘要== | ||
{{信息题|最小生成树|http://www.codevs.cn/problem/1078/|1|100|time=2015-7-22 20:08:48}} | {{信息题|最小生成树|http://www.codevs.cn/problem/1078/|1|100|time=2015-7-22 20:08:48}} |
题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
---|---|---|---|---|---|
最小生成树 | ★☆☆☆☆ | 答案正确 | 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; } |