| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 最小生成树 | ★☆☆☆☆ | 答案正确 | 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;
}
|
CloudLunar