那就用kruskal
by BMTXLRC @ 2022-07-20 20:28:19
重边就是端点相同的边，对于最小生成树来说应该是不影响的，因为只会取边权最小的一条边
by awcyvan @ 2022-07-20 20:28:22
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
int maps[114][514];
bool flag[114514]={0};
int cost[114514];
int minc=INT_MAX;
int nxt;
int sum=0;
bool book;
void prim()
{
for(int i=1;i<=n;i++)
{
cost[i]=maps[1][i];//将结点一到其他结点的权值保存在cost中
}
flag[1]=1;//标记已访问
for(int i=1;i<=n-1;i++)//1已经访问过了，所以循环n-1次
{
int minc=INT_MAX;
for(int j=1;j<=n;j++)
{
if(flag[j]==0 && cost[j]< minc)
{
minc=cost[j];//将该结点到其他结点的权值相互做比较，取最小值
nxt=j;//nxt标记下一个结点
}
}
if(minc==INT_MAX)
{
book=1;
break;
}
flag[nxt]=1;
sum+=cost[nxt];//将到下一个结点的权值累加
for(int j=1;j<=n;j++)
{
if(flag[j]==0 && maps[nxt][j]<cost[j])//如果这点没有被访问过，而且这个点到任意一点的距离比现在到树的距离近那么更新
{
cost[j]=maps[nxt][j];//将下一个结点到其他结点的权值存在cost中
}
}
}
if(book==1)
{
cout<<"orz";
return;
}
cout<<sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j) maps[i][j]=INT_MAX;
else maps[i][j]=0;
}
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
maps[x][y]=z;
maps[y][x]=z;
}
prim();
return 0;
}
```
by slipknot @ 2022-07-20 20:31:45
@[awcyvan](/user/691465) 我这段却只得30分，大佬能看看哪出问题了吗
by slipknot @ 2022-07-20 20:32:29
邻接矩阵……有重边的话输入时保留最小的一个边权，因为更大的不会有贡献
by awcyvan @ 2022-07-20 20:34:16
@[slipknot](/user/543953) 那啥，时间过得了吗
by Mr_Terminator @ 2022-07-20 20:34:36
存边时取min(map\[x]\[y],z)
by awcyvan @ 2022-07-20 20:35:02
似乎是O(n^2+m)的暴力版本，拿个堆或者优先队列什么的维护一下最小距离吧
by awcyvan @ 2022-07-20 20:37:41
堆优化的方式类似 Dijkstra 的堆优化，但如果使用二叉堆等不支持 O(1) decrease-key 的堆，复杂度就不优于 Kruskal，常数也比 Kruskal 大。所以，一般情况下都使用 Kruskal 算法，在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但 不一定 实际跑得更快。
我的建议是跑 Kruskal
by awcyvan @ 2022-07-20 20:38:53
@[awcyvan](/user/691465) 好的，感谢大佬，等这个过了之后再用Kruskal走一遍
by slipknot @ 2022-07-20 20:40:31