HNUST-OJ-1807 算法7-9：最小生成树

原题复刻

思想的火花 

1.int prim()：

    fill(d,d+MAX,INF);//初始化所有点到原点0的距离为INF，无穷大d[0]=0;//原点到原点距离为0int ans=0;//ans用以存储从原点到所有点的最小距离for(int i=0; i<n; i++){int u=-1,minn=INF;//u表示是否存在一点未访问，且到原点距离最小的一点for(int j=0; j<n; j++)if(vi[j]==0&&d[j]<minn)u=j,minn=d[j];//按照if条件语句进行更新if(u==-1)return -1;//一点都找不到满足条件直接返回（无法生成最小生成树）vi[u]=1;//标记找到的uans+=d[u];总距离增加；for(int v=0; v<n; v++)if(vi[v]==0&&g[u][v]!=INF&&g[u][v]<d[v])d[v]=g[u][v];//是否存在一点在u作为辅助点的前提下拥有到原点更短的距离}return ans;

2.

if(g[i][j]==0)g[i][j]=INF;

依照题目要求，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。

为0时用INF进行更新

代码实现 

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000
#define INF 1e+7
int n,g[MAX][MAX];
int d[MAX];
bool vi[MAX];
int prim()
{fill(d,d+MAX,INF);d[0]=0;int ans=0;for(int i=0; i<n; i++){int u=-1,minn=INF;for(int j=0; j<n; j++)if(vi[j]==0&&d[j]<minn)u=j,minn=d[j];if(u==-1)return -1;vi[u]=1;ans+=d[u];for(int v=0; v<n; v++)if(vi[v]==0&&g[u][v]!=INF&&g[u][v]<d[v])d[v]=g[u][v];}return ans;}
int main()
{cin>>n;//fill(g[0],g[0]+MAX*MAX,INF);for(int i=0; i<n; i++)for(int j=0; j<n; j++){cin>>g[i][j];if(g[i][j]==0)g[i][j]=INF;}cout<<prim();}