超级源点
在最短路算法中,超级源点解决的是多起点,多终点的问题,而在最小生成树中,解决的是点自身权值的问题
此题是裸的超级源点问题
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 305, INF = 0x3f3f3f3f;
int g[N][N];
int n;
int dist[N];
bool st[N];
int prim()
{
memset(dist,0x3f,sizeof dist);
int res=0;
for(int i=0;i<=n;i++)
{
int t=-1;
for(int i=0;i<=n;i++)
if(!st[i]&&(t==-1||dist[t]>dist[i]))
t=i;
if(i&&dist[t]==INF)break;
st[t]=true;
if(i)res+=dist[t];
for(int i=0;i<=n;i++)dist[i]=min(dist[i],g[t][i]);
}
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>g[0][i];
g[i][0]=g[0][i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];
cout<<prim()<<endl;
return 0;
}