【ybtoj】新的开始
题目描述
输入格式
输出格式
输出仅一个整数，表示让所有矿井获得充足电能的最小花费。
样例输入
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
样例输出
9
样例解释
小F可以选择在4号矿井建立发电站然后把所有矿井都与其建立电网，总花费是3+2+2+2=9。
解题思路
经典的prim求最小生成树
Code
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,tot,x,maxn=99999999,minn=99999999,s,e,c[2001],k;
bool b[2001];
int f[2001][2001];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>f[0][i];
f[i][0]=f[0][i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>f[i][j];
for(int i=1;i<=n;i++)
f[i][i]=maxn;
tot=0;
b[0]=true;
c[0]=0;
for(int i=1;i<=n;i++)
c[i]=f[0][i];
for(int i=1;i<=n;i++)
{
minn=maxn;
k=0;
for(int j=1;j<=n;j++)
if((!b[j])&&(c[j]<minn))
{
minn=c[j];
k=j;
}
tot+=c[k];
b[k]=true;
for(int j=1;j<=n;j++)
if(f[k][j]<c[j])
c[j]=f[k][j];
}
cout<<tot;
return 0;
}