@[刘芝麻](/space/show?uid=208269)
~~都9102年,还有人用pas~~
看不懂pas,放出我的代码QAQ
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=105;
int n,ans;
struct node
{
int to,v;
};
vector <node> edge[MAXN];
bool visit[MAXN];
struct cmp//重载为小根堆,注意语法
{
bool operator()(const node& x,const node& y)const
{//注意重载的是()运算符;而在结构体内重载是<运算符
return x.v>y.v;
}
};
void input(void)
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
cin>>x;
if(x)//按题目要求建无向图
{
edge[i].push_back((node){j,x});
edge[j].push_back((node){i,x});
}
}
}
void prim(void)
{
priority_queue <node,vector<node>,cmp> q;
visit[1]=true;//从第一个点开始,为起点
for(vector<node>::iterator it=edge[1].begin();it!=edge[1].end();it++)
q.push(*it);//把第一个点相关的点进堆,之后好拿出来用
while(!q.empty())//开始遍历
{
const node tmp=q.top();
q.pop();
if(visit[tmp.to])//访问过就跳过
continue;
visit[tmp.to]=true;
ans+=tmp.v;//别忘了存储答案
for(vector<node>::iterator it=edge[tmp.to].begin();it!=edge[tmp.to].end();it++)
if(!visit[it->to])
q.push(*it);//再次进堆
}
}
int main()
{
input();
prim();
cout<<ans;
return 0;
}
```
by Hexarhy @ 2019-08-09 10:28:24
@[HyyypRtf06](/space/show?uid=80049) 谢谢(~~虽然我也几乎看不懂~~)
by 刘芝麻 @ 2019-08-09 10:44:31