rc_Taurus @ 2023-02-03 14:42:18
#include<bits/stdc++.h>
#pragma GCC optmize(2)
using namespace std;
#define int long long
#define inf 2147483647
int n,m,edge[5005][5005],lowcost[5005],closest[5005],sum,cnt=1;
bool flag[5005];
void prim(int n){//n表示有n个节点
flag[1]=true;
for(int i=1;i<=n;i++){
if(i==1)lowcost[i]=0;
else{
flag[i]=false;
closest[i]=1;
lowcost[i]=edge[1][i];
}
}
//下面就有点类似Dijkstra的代码
for(int i=1;i<n;i++){
int temp=inf,t=-1;
for(int j=1;j<=n;j++){
if((!flag[j])&&lowcost[j]<temp){
t=j;
temp=lowcost[j];
}
}
if(t==-1)break;
flag[t]=true;
sum+=temp;
cnt++;
//更新
for(int j=1;j<=n;j++){
if((!flag[i])&&(lowcost[j]>edge[t][j])){
lowcost[j]=edge[t][j];
closest[j]=t;
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)edge[i][j]=0;
else edge[i][j]=inf;
}
}
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
edge[u][v]=edge[v][u]=w;
}
prim(n);
if(cnt==n)cout<<sum;else cout<<"orz";
return 0;
}
by rc_Taurus @ 2023-02-03 14:44:10
lowcost[j]表示集合U-V中点j到集合U的最短距离。
closet[j]表示集合U-V中点j到集合U的最邻近点
by __cheems__ @ 2023-03-14 15:52:10
prim算法应该还要再加个堆优化,不然会TLE。