Prim
123456789101112131415161718192021222324252627282930313233343536373839404142
#include<bits/stdc++.h>
using namespace std;
int V,E,m,ans=0;
int v[101],e[1000],w[1000],d[100],father[100]={0};
bool T[100]={0};
void Prim(int u){
if(m==V) return;
for(int i=v[u];i<v[u+1];++i){
if(d[e[i]]>w[i]){
d[e[i]]=w[i];
father[e[i]]=u;
}
}
int d_min=0x7fffffff,v_min=102;
for(int i=0;i<V;++i){
if(!T[i]&&d[i]<d_min){
d_min=d[i];
v_min=i;
}
}
ans+=d_min;
cout<<"["<<father[v_min]<<"->"<<v_min<<"]";
T[v_min]=1;
++m;
Prim(v_min);
}
int main (){
cin>>V>>E;
for(int i=0;i<=V;++i){
cin>>v[i];
d[i]=0x7fffffff;
}
for(int i=0;i<E;++i) cin>>e[i];
for(int i=0;i<E;++i) cin>>w[i];
T[0]=1;
m=1;
Prim(0);
cout<<" "<<ans<<endl;
return 0;
}
Cpp
INFO